Advertisement
K_Y_M_bl_C

Untitled

Oct 9th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> pii;
  7. typedef vector<int> vi;
  8.  
  9. #define X first
  10. #define Y second
  11. #define inb push_back
  12. #define mk make_pair
  13. #define all(v) v.begin(), v.end()
  14. #define sqr(x) (x) * (x)
  15. #define y1 zapadupal
  16.  
  17. int solve();
  18.  
  19. int main()
  20. {
  21.     solve();
  22.     return 0;
  23. }
  24.  
  25. mt19937 rnd(time(0));
  26.  
  27. int solve()
  28. {
  29.     int n;
  30.     scanf("%d", &n);
  31.     vector<vi> a(n, vi(n)), xpr(n, vi(n));
  32.     unordered_map<int, int> kek;
  33.     for (int i = 0; i < (int)kek.size(); ++i)
  34.     {
  35.         kek[i] = abs((int)rnd());
  36.     }
  37.     for (int i = 0; i < n; ++i)
  38.     {
  39.         for (int j = 0; j < n; ++j)
  40.         {
  41.             scanf("%d", &a[i][j]);
  42.             --a[i][j];
  43.             if (kek.find(a[i][j]) == kek.end())
  44.             {
  45.                 kek[a[i][j]] = rnd();
  46.             }
  47.             a[i][j] = kek[a[i][j]];
  48.             xpr[i][j] = a[i][j];
  49.             if (i)
  50.                 xpr[i][j] ^= xpr[i - 1][j];
  51.             if (j)
  52.                 xpr[i][j] ^= xpr[i][j - 1];
  53.             if (i && j)
  54.                 xpr[i][j] ^= xpr[i - 1][j - 1];
  55.         }
  56.     }
  57.     auto getxor = [&](int x, int y, int x1, int y1)
  58.     {
  59.         int ans = xpr[x1][y1];
  60.         if (x)
  61.             ans ^= xpr[x - 1][y1];
  62.         if (y)
  63.             ans ^= xpr[x1][y - 1];
  64.         if (x && y)
  65.             ans ^= xpr[x - 1][y - 1];
  66.         return ans;
  67.     };
  68.     int ansx = 0, ansy = 0;
  69.     auto check = [&](int x)
  70.     {
  71.         for (int i = 1; i + x < n; ++i)
  72.         {
  73.             for (int j = 1; j + x < n; ++j)
  74.             {
  75.                 if (getxor(i, j, i + x - 1, j + x - 1) == 0)
  76.                 {
  77.                     ansx = i + 1, ansy = j + 1;
  78.                     return 1;
  79.                 }
  80.             }
  81.         }
  82.         return 0;
  83.     };
  84.     int l = n - 2;
  85.     while (!check(l))
  86.         l -= 2;
  87.     printf("%d %d %d\n", l, ansx, ansy);
  88.     return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement