Submission #770501

#TimeUsernameProblemLanguageResultExecution timeMemory
770501GrindMachineThe Kingdom of JOIOI (JOI17_joioi)C++17
100 / 100
662 ms31792 KiB
// Om Namah Shivaya #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: https://codeforces.com/blog/entry/50413 (for 60 points): stress tested to identify the bug: https://oj.uz/submission/767335 didnt set the bounds for the binary search properly (wrote n instead of m) idea for 100 points: minimize the maximum => think of b.s how to write the ok() function? let's say we are checking if ans <= k mn and mx are in diff territories all values in the min territory have to be <= mn+k all values in the max territory have to be >= mx-k the upper left col can belong to either the mn/mx territory and the length chosen in each row could be increasing/decreasing try out all 4 possibilities, check if possible */ const int MOD = 1e9 + 7; const int N = 2e3 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; ll a[N][N]; void solve(int test_case) { ll n,m; cin >> n >> m; rep1(i,n) rep1(j,m) cin >> a[i][j]; ll mn = inf2, mx = -inf2; rep1(i,n){ rep1(j,m){ amin(mn,a[i][j]); amax(mx,a[i][j]); } } auto ok = [&](ll k){ // min territory, decreasing { ll prev_len = inf2; bool flag = true; rep1(i,n){ ll len = 0; rep1(j,m){ if(a[i][j] <= mn+k){ len++; } else{ break; } } amin(len,prev_len); prev_len = len; for(int j = len+1; j <= m; ++j){ if(a[i][j] < mx-k){ flag = false; } } } if(flag) return true; } // min territory, increasing { ll prev_len = inf2; bool flag = true; rev(i,n,1){ ll len = 0; rep1(j,m){ if(a[i][j] <= mn+k){ len++; } else{ break; } } amin(len,prev_len); prev_len = len; for(int j = len+1; j <= m; ++j){ if(a[i][j] < mx-k){ flag = false; } } } if(flag) return true; } // max territory, decreasing { ll prev_len = inf2; bool flag = true; rep1(i,n){ ll len = 0; rep1(j,m){ if(a[i][j] >= mx-k){ len++; } else{ break; } } amin(len,prev_len); prev_len = len; for(int j = len+1; j <= m; ++j){ if(a[i][j] > mn+k){ flag = false; } } } if(flag) return true; } // max territory, increasing { ll prev_len = inf2; bool flag = true; rev(i,n,1){ ll len = 0; rep1(j,m){ if(a[i][j] >= mx-k){ len++; } else{ break; } } amin(len,prev_len); prev_len = len; for(int j = len+1; j <= m; ++j){ if(a[i][j] > mn+k){ flag = false; } } } if(flag) return true; } return false; }; ll l = 0, r = inf1; ll ans = -1; while(l <= r){ ll mid = (l+r) >> 1; if(ok(mid)){ ans = mid; r = mid-1; } else{ l = mid+1; } } cout << ans << endl; } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...