SHARE
TWEET

Untitled

a guest Oct 17th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #ifndef ACMTUYO
  6. #define cin lala
  7. ifstream cin;
  8. #define cout coco
  9. ofstream coco;
  10. #endif
  11.  
  12. #define forn(i, n) for(int i = 0; i < int(n); ++i)
  13.  
  14. typedef long long int ll;
  15.  
  16. ll at(vector<vector<ll>> &ns, int x, int y) {
  17.     if(x >= int(ns.size())) return 0;
  18.     if(x < 0) return 0;
  19.     if(y >= int(ns[0].size())) return 0;
  20.     if(y < 0) return 0;
  21.     return ns[x][y];
  22. }
  23.  
  24. ll sqrte(ll k) {
  25.     ll lo = 1;
  26.     ll hi = k;
  27.     while(hi - lo > 1) {
  28.         ll mid = (hi+lo)/2;
  29.         if(mid*mid >= k) hi = mid;
  30.         else lo = mid;
  31.     }
  32.     return hi;
  33. }
  34.  
  35. vector<ll> divs(ll k) {
  36.     cerr << k << endl;
  37.     vector<ll> res;
  38.     for(ll i = 1; i * i <= k; ++i) {
  39.         if(k % i == 0) {
  40.             ll s = sqrte(i);
  41.             if(s*s == i) res.push_back(i);
  42.             s = sqrte(k / i);
  43.             if(i*i != k && s*s == k/i) res.push_back(s);
  44.         }
  45.     }
  46.     return res;
  47. }
  48.  
  49. int main() {
  50.     #ifndef ACMTUYO
  51.     cin = ifstream("injurious.in");
  52.     cout = ofstream("injurious.out");
  53.     #endif
  54.     int n, m;
  55.     cin >> n >> m;
  56.     vector<vector<ll>> mat(n, vector<ll>(m));
  57.     ll sum = 0;
  58.     forn(i, n) forn(j, m) {
  59.         cin >> mat[i][j];
  60.         sum += mat[i][j];
  61.     }
  62.     vector<vector<ll>> filt(m, vector<ll>(m));
  63.     for(ll _k : divs(sum)) {
  64.         int k = int(_k);
  65.         cerr << k << endl;
  66.         vector<pair<ll, pair<int, int>>> curr;
  67.         forn(i, n) forn(j, m) {
  68.             ll d = at(mat, i, j-1) + at(mat, i-1, j) - at(mat, i-1, j-1);
  69.             d += at(filt, i-k, j-k) - at(filt, i, j-k) - at(filt, i-k, j);
  70.             filt[i][j] = d - mat[i][j];
  71.             if(i+k <= n && j+k <= m) {
  72.                 if(filt[i][j] != 0) {
  73.                     curr.push_back({filt[i][j], {i, j}});
  74.                 }
  75.             } else {
  76.                 if(filt[i][j] != 0) {
  77.                     cerr << "CERO FUERA" << endl;
  78.                     goto noanda;
  79.                 }
  80.             }
  81.         }
  82.         sort(curr.begin(), curr.end());
  83.         forn(i, curr.size()) {
  84.             if(curr[i].first != i+1) {
  85.                 cout << "MAL" << endl;
  86.                 goto noanda;
  87.             }
  88.         }
  89.         for(auto p : curr) cout << p.second.first << " " << p.second.second << endl;
  90.         return 0;
  91.         noanda:;
  92.     }
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top