Submission #1188061

#TimeUsernameProblemLanguageResultExecution timeMemory
1188061maxFedorchukThe Kingdom of JOIOI (JOI17_joioi)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; const long long MX=2e3+10; vector < pair < int , pair < int , int > > > ms1; int a[MX][MX],mtrin[MX][MX],u[MX*MX]; int n,m; int lstzr; int clc() { /* for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<a[i][j]<<" "; } cout<<"\n"; } */ ms1.clear(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ms1.push_back({a[i][j],{i,j}}); } } sort(ms1.begin(),ms1.end()); for(int i=0;i<n*m;i++) { mtrin[ms1[i].second.first][ms1[i].second.second]=i; u[i]=0; } lstzr=n*m-1; int mn1=n*m-1; int rt=ms1.back().first-ms1[0].first; while(lstzr) { int i=ms1[lstzr].second.first; while(i>0 && !u[mtrin[i][ms1[lstzr].second.second]]) { int j=ms1[lstzr].second.second; while(j>0 && !u[mtrin[i][j]]) { u[mtrin[i][j]]=1; mn1=min(mn1,mtrin[i][i]); j--; } i--; } while(u[lstzr] && lstzr>0) { lstzr--; } if(ms1[mn1].first==ms1[0].first) { break; } rt=min(rt,max(ms1.back().first-ms1[mn1].first,ms1[lstzr].first-ms1[0].first)); } return rt; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } int ans=clc(); for(int i=1;i<=n;i++) { for(int j=1;j<=m/2;j++) { swap(a[i][j],a[i][m-j+1]); } } ans=min(ans,clc()); for(int i=1;i<=n/2;i++) { for(int j=1;j<=m;j++) { swap(a[n-i+1][j],a[i][j]); } } ans=min(ans,clc()); for(int i=1;i<=n;i++) { for(int j=1;j<=m/2;j++) { swap(a[i][j],a[i][m-j+1]); } } ans=min(ans,clc()); cout<<ans<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...