Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef ACMTUYO
- #define cin lala
- ifstream cin;
- #define cout coco
- ofstream coco;
- #endif
- #define forn(i, n) for(int i = 0; i < int(n); ++i)
- typedef long long int ll;
- ll at(vector<vector<ll>> &ns, int x, int y) {
- if(x >= int(ns.size())) return 0;
- if(x < 0) return 0;
- if(y >= int(ns[0].size())) return 0;
- if(y < 0) return 0;
- return ns[x][y];
- }
- ll sqrte(ll k) {
- ll lo = 1;
- ll hi = k;
- while(hi - lo > 1) {
- ll mid = (hi+lo)/2;
- if(mid*mid >= k) hi = mid;
- else lo = mid;
- }
- return hi;
- }
- vector<ll> divs(ll k) {
- cerr << k << endl;
- vector<ll> res;
- for(ll i = 1; i * i <= k; ++i) {
- if(k % i == 0) {
- ll s = sqrte(i);
- if(s*s == i) res.push_back(i);
- s = sqrte(k / i);
- if(i*i != k && s*s == k/i) res.push_back(s);
- }
- }
- return res;
- }
- int main() {
- #ifndef ACMTUYO
- cin = ifstream("injurious.in");
- cout = ofstream("injurious.out");
- #endif
- int n, m;
- cin >> n >> m;
- vector<vector<ll>> mat(n, vector<ll>(m));
- ll sum = 0;
- forn(i, n) forn(j, m) {
- cin >> mat[i][j];
- sum += mat[i][j];
- }
- vector<vector<ll>> filt(m, vector<ll>(m));
- for(ll _k : divs(sum)) {
- int k = int(_k);
- cerr << k << endl;
- vector<pair<ll, pair<int, int>>> curr;
- forn(i, n) forn(j, m) {
- ll d = at(mat, i, j-1) + at(mat, i-1, j) - at(mat, i-1, j-1);
- d += at(filt, i-k, j-k) - at(filt, i, j-k) - at(filt, i-k, j);
- filt[i][j] = d - mat[i][j];
- if(i+k <= n && j+k <= m) {
- if(filt[i][j] != 0) {
- curr.push_back({filt[i][j], {i, j}});
- }
- } else {
- if(filt[i][j] != 0) {
- cerr << "CERO FUERA" << endl;
- goto noanda;
- }
- }
- }
- sort(curr.begin(), curr.end());
- forn(i, curr.size()) {
- if(curr[i].first != i+1) {
- cout << "MAL" << endl;
- goto noanda;
- }
- }
- for(auto p : curr) cout << p.second.first << " " << p.second.second << endl;
- return 0;
- noanda:;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement