Submission #924947

#	Time	Username	Problem	Language	Result	Execution time	Memory
924947		niter	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	21 ms	100956 KiB

joioi

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define BAE(x) x.begin(), x.end()
#define unisort(x) sort(BAE(x)); x.resize(unique(BAE(x)) - x.begin())
using namespace std;
typedef long long ll;

const int mxn = 2005;
const int mxA = 4050000;

int n, m, area, ans;
int a[mxn][mxn];
int col[mxA];
vector<int> E[mxA];

inline int pos(int x, int y){
    return x * m + y;
}

bool dfs(int v){
//    cout << "v = " << v << '\n';
    for(auto &i:E[v]){
        if(col[i] == 0){
            col[i] = (col[v] == 1) ? 2 : 1;
            if(!dfs(i)){
                return false;
            }
        }
        else if(col[i] == col[v]){
            return false;
        }
    }
    return true;
}

inline bool check(int val){
    loop(i,0,area){
        E[i].clear();
        col[i] = 0;
    }
    loop(i,0,n){
        loop(j,0,m){
            loop(k,i,n){
                loop(l,j,m){
                    if(abs(a[i][j] - a[k][l]) > val){
//                        cout << "(" << i << ", " << j << ") (" << k << ", " << l << ")\n";
                        E[pos(i, j)].pb(pos(k, l));
                        E[pos(k, l)].pb(pos(i, j));
                    }
                }
            }
        }
    }
    loop(i,0,area){
        if(col[i] == 0 && (!E[i].empty())){
//            cout << "i = " << i << '\n';
            col[i] = 1; // 1:white, 2:black
            if(!dfs(i)) return false;
        }
    }
//    loop(i,0,n){
//        loop(j,0,m) cout << col[pos(i, j)] << ' ';
//        cout << endl;
//    }
    loop(i,0,n){
        int flip = -1, tmp = 0;
        loop(j,0,m){
            if(col[pos(i, j)] == 0) continue;

            if(flip == -1){
                tmp = col[pos(i, j)];
                flip = 0;
            }
            else if(tmp != col[pos(i, j)]){
                tmp = col[pos(i, j)];
                flip += 1;
            }
        }
        if(flip >= 2) return false;
    }


    loop(j,0,m){
        int flip = -1, tmp = 0;
        loop(i,0,n){
            if(col[pos(i, j)] == 0) continue;

            if(flip == -1){
                tmp = col[pos(i, j)];
                flip = 0;
            }
            else if(tmp != col[pos(i, j)]){
                tmp = col[pos(i, j)];
                flip += 1;
            }
        }
        if(flip >= 2) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
//    freopen("in.txt", "r", stdin);
    cin >> n >> m;
    area = n * m;
    loop(i,0,n){
        loop(j,0,m){
            cin >> a[i][j];
        }
    }
    vector<int> v;
    loop(i,0,n){
        loop(j,0,m){
            loop(k,i,n){
                loop(l,j,m){
                    v.pb(abs(a[i][j] - a[k][l]));
                    ans = max(ans, abs(a[i][j] - a[k][l]));
                }
            }
        }
    }
    unisort(v);
//    for(auto &i:v){
//        cout << i << ' ';
//    } cout << endl;
    int l = 0, r = v.size() - 1, mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(v[mid])){
            ans = v[mid];
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    assert(ans != 11);
    cout << ans << '\n';
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40