Submission #250452

#TimeUsernameProblemLanguageResultExecution timeMemory
250452fivefourthreeoneThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
229 ms16248 KiB
#include <bits/stdc++.h> #define owo(i,a, b) for(int i=(a); i<(b); ++i) #define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i) #define senpai push_back #define ttgl pair<int, int> #define ayaya cout<<"ayaya~"<<endl using namespace std; using ll = long long; using ld = long double; const ll MOD = 998244353; int gcd(int a,int b){return b?gcd(b,a%b):a;} ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;} ll modInv(ll a){return binpow(a, MOD-2);} const double PI = acos(-1); const int INF = 0x3f3f3f3f; const int NINF = 0xc0c0c0c0; const ll INFLL = 0x3f3f3f3f3f3f3f3f; const ll NINFLL = 0xc0c0c0c0c0c0c0c0; const int mxN = 2001; int comp[mxN*mxN]; int board[mxN][mxN]; int cnt[mxN*mxN]; int save[mxN*mxN]; map<int, int>mp; set<int> aaa; int w, h; int mx = 0; int mn = INF; int idx = 0; bool check(int val) { memset(cnt, 0, sizeof(cnt)); int prev = INF; owo(i, 0, h) { int curr = -1; owo(j, 0, w) { if(mx-comp[board[i][j]]<=val&&j<=prev) { cnt[board[i][j]]++; curr = j; continue; } break; } prev = curr; } uwu(i, idx, 0) { if(cnt[i]==save[i]) { if(i==0) return true; continue; } if(comp[i]-mn<=val)return true; break; } memset(cnt, 0, sizeof(cnt)); prev = -1; owo(i, 0, w) { int curr = INF; uwu(j, h, 0) { if(mx-comp[board[j][i]]<=val&&j>=prev) { cnt[board[j][i]]++; curr = j; continue; } break; } prev = curr; } uwu(i, idx, 0) { if(cnt[i]==save[i]) { if(i==0) return true; continue; } if(comp[i]-mn<=val)return true; break; } memset(cnt, 0, sizeof(cnt)); prev = -1; uwu(i, h, 0) { int curr = INF; uwu(j, w, 0) { if(mx-comp[board[i][j]]<=val&&j>=prev) { cnt[board[i][j]]++; curr = j; continue; } break; } prev = curr; } uwu(i, idx, 0) { if(cnt[i]==save[i]) { if(i==0) return true; continue; } if(comp[i]-mn<=val)return true; break; } memset(cnt, 0, sizeof(cnt)); prev = INF; uwu(i, w, 0) { int curr = -1; owo(j, 0, h) { if(mx-comp[board[j][i]]<=val&&j<=prev) { cnt[board[i][j]]++; curr = j; continue; } break; } prev = curr; } uwu(i, idx, 0) { if(cnt[i]==save[i]) { if(i==0) return true; continue; } if(comp[i]-mn<=val)return true; break; } return false; } int main() { //freopen("exercise.in", "r", stdin); //freopen("exercise.out", "w", stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); cin.tie(0)->sync_with_stdio(0); cin>>h>>w; owo(i, 0, h) { owo(j, 0, w) { cin>>board[i][j]; aaa.insert(board[i][j]); mx = max(mx, board[i][j]); mn = min(mn, board[i][j]); } } auto it = aaa.begin(); while(it!=aaa.end()) { mp[*it] = idx; comp[idx] = *it; idx++; it++; } owo(i, 0, h) { owo(j, 0, w) { board[i][j] = mp[board[i][j]]; save[board[i][j]]++; } } int l = 0; int r = mx-mn; while(l<r) { int mid = (l+r)/2; if(check(mid)) { r = mid; }else{ l = mid+1; } } cout<<l<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...