Submission #1019317

#TimeUsernameProblemLanguageResultExecution timeMemory
1019317vjudge1The Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> #include <algorithm> #include <iostream> #include <string> using namespace std; #define FOR(i,n) for(int i=0;i<n;i++) #define ROF(i,m,n) for(int i=m;i<=n;i++) #define vi vector<int> #define pb push_back #define alle(a) a.begin(),a.end() #define rall(n) rbegin(n),rend(n) #define int long long #define vecs vector<int> #define ll long long #define ss second #define ff first const int INF = 1e9; const int MOD = 1e9 + 7; void solve(){ int n , m; cin>>n>>m; vector <vector<int>> a(n,vector <int> (m)); vector <vector<int>> color(n,vector<int> (m)); int mx = 0; int mn = INF; int y1,y2; int g1,g2; int ans = 0; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ cin>>a[i][j]; if(a[i][j] > mx){ mx = a[i][j]; y1 = i; g1 = j; } if(a[i][i] < mn){ mn = a[i][j]; y2 = i; g2 = j; } } } color[y1][g1] = 1; color[y2][g2] = 2; auto check = [&](int m1){ color[y1][g1] = 1; color[y2][g2] = 2; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(mx - a[i][j] <= m&& a[i][j] - mn <= m1){ color[i][j] = 3; } if(mx - a[i][j] <= m1){ color[i][j] = 1; } else if(a[i][j] - mn <= m1){ color[i][j] = 2; } } } if(color[0][0] == 1||color[0][0] == 3){ for(int i =0;i < n;i++){ for(int j = 0;j < m;j++){ if(color[i][j] == 1){ for(int q = i;q >= 0;q--){ color[q][j] = 1; } for(int q = j;q >= 0;q--){ color[i][q] = 1; } } } } int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(color[i][j] == 3){ color[i][j] = 2; } if(color[i][j] == 1){ mx1 = max(mx1,a[i][j]); mn1 = min(mn1,a[i][j]); } else if(color[i][j] == 2){ mx2 = max(mx2,a[i][j]); mn2 = min(mn2,a[i][j]); } } } if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){ return true; } } if(color[0][m - 1] == 1||color[0][m - 1] == 3){ for(int i =0;i < n;i++){ for(int j = 0;j < m;j++){ if(color[i][j] == 1){ for(int q = i;q >= 0;q--){ color[q][j] = 1; } for(int q = j;q < m;q++){ color[i][q] = 1; } } } } int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(color[i][j] == 3){ color[i][j] = 2; } if(color[i][j] == 1){ mx1 = max(mx1,a[i][j]); mn1 = min(mn1,a[i][j]); } else if(color[i][j] == 2){ mx2 = max(mx2,a[i][j]); mn2 = min(mn2,a[i][j]); } } } if((mx1 - mn1 >= m1) && (mx2 - mn2 >= m1)){ return true; } } if(color[n - 1][0] == 1||color[n - 1][0] == 3){ for(int i =0;i < n;i++){ for(int j = 0;j < m;j++){ if(color[i][j] == 1){ for(int q = i;q < n;q++){ color[q][j] = 1; } for(int q = j;q >= 0;q--){ color[i][q] = 1; } } } } int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(color[i][j] == 3){ color[i][j] = 2; } if(color[i][j] == 1){ mx1 = max(mx1,a[i][j]); mn1 = min(mn1,a[i][j]); } else if(color[i][j] == 2){ mx2 = max(mx2,a[i][j]); mn2 = min(mn2,a[i][j]); } } } if((mx1 - mn1 >= m1) && (mx2 - mn2 >= m1)){ return true; } } if(color[n - 1][m] == 1||color[n - 1][m - 1] == 3){ for(int i =0;i < n;i++){ for(int j = 0;j < m;j++){ if(color[i][j] == 1){ for(int q = i;q < n;q++){ color[q][j] = 1; } for(int q = j;q < m;q++){ color[i][q] = 1; } } } } int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(color[i][j] == 3){ color[i][j] = 2; } if(color[i][j] == 1){ mx1 = max(mx1,a[i][j]); mn1 = min(mn1,a[i][j]); } else if(color[i][j] == 2){ mx2 = max(mx2,a[i][j]); mn2 = min(mn2,a[i][j]); } } } if((mx1 - mn1 >= m1) && (mx2 - mn2 >= m1)){ return true; } } return false; }; int l = 0,r = mx - mn + 1; while(1 < r - l){ int m = (l + r) >> 1; if(check(m)){ r = m; } else{ l = m; } } if(check(l)){ cout<<l; } else{ cout<<r; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; while (t--) { solve(); } return 0; }

Compilation message (stderr)

joioi.cpp: In function 'void solve()':
joioi.cpp:28:9: warning: unused variable 'ans' [-Wunused-variable]
   28 |     int ans = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...