Guest User

Untitled

a guest
Oct 17th, 2019
88
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