Submission #979002

#TimeUsernameProblemLanguageResultExecution timeMemory
9790028pete8The Kingdom of JOIOI (JOI17_joioi)C++17
100 / 100
1512 ms135144 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<limits.h> #include <cassert> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> #include <cstdlib> #include <cstdint> using namespace std; #define ll long long #define f first //#define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; //#define int long long #define double long double const int mxn=1e5,inf=1e9,minf=-1e9,Mxn=1e7; int grid[2002][2002],bound[2002],grid2[2002][2002];//keep boundary on left comp int mxbound[2002],mxrange=0; bool have[2002]; int mx=minf,mn=inf; vector<pii>mxpos,mnpos; int n,m; int solve(int mode){//1==mn on left vector<pair<int,pii>>v; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){ if(grid[i][j]!=mn&&grid[i][j]!=mx)v.pb({max(mx-grid[i][j],grid[i][j]-mn),{i,j}}); } sort(rall(v)); int amx=0;//another mx for(auto i:v){ bool side=(mx-grid[i.s.f][i.s.s]>grid[i.s.f][i.s.s]-mn);//if 1 then we need to go to mn if(mx-grid[i.s.f][i.s.s]==grid[i.s.f][i.s.s]-mn)return mx-grid[i.s.f][i.s.s]; if(i.f<amx)return amx; amx=max(amx,mxrange-i.f); side^=mode; if(side){ //right if(bound[i.s.f]<i.s.s)mxbound[i.s.f]=min(i.s.s,mxbound[i.s.f]);//alrdy valid else return i.f; //we cant decrease the bound? } else{ //left if(bound[i.s.f]>=i.s.s);//alrdy valid else{ while(bound[i.s.f]<i.s.s){ int cur=i.s.f,b=inf; while(cur>=1&&bound[cur]==bound[i.s.f])b=min(b,mxbound[cur]),cur--; if(bound[i.s.f]+1>=b)return i.f; for(int j=cur+1;j<=i.s.f;j++)bound[j]++; } //we can increase the bound } } } return amx; } int solvemain(){ int ans=inf; mxpos.clear(); mnpos.clear(); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){ if(grid[i][j]==mx)mxpos.pb({i,j}); if(grid[i][j]==mn)mnpos.pb({i,j}); } for(int i=1;i<=n;i++)bound[i]=0,mxbound[i]=m+1; bound[1]=1;//min bound (atleast one exist) mxbound[n]=m; for(auto i:mxpos)bound[i.f]=max(bound[i.f],i.s); for(int i=n;i>=1;i--)bound[i]=max(bound[i],bound[i+1]); bool valid=1; for(auto i:mnpos)valid&=(bound[i.f]<i.s),mxbound[i.f]=min(mxbound[i.f],i.s); if(valid)ans=min(ans,solve(0)); //put mn of left comp for(int i=1;i<=n;i++)bound[i]=0,mxbound[i]=m+1; bound[1]=1; mxbound[n]=m; for(auto i:mnpos)bound[i.f]=max(bound[i.f],i.s); for(int i=n;i>=1;i--)bound[i]=max(bound[i],bound[i+1]); valid=1; for(auto i:mxpos)valid&=(bound[i.f]<i.s),mxbound[i.f]=min(mxbound[i.f],i.s);; if(valid)ans=min(ans,solve(1)); return ans; } //will this work?????????? int32_t main(){ fastio cin>>n>>m; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){ cin>>grid[i][j],mx=max(mx,grid[i][j]),mn=min(mn,grid[i][j]); grid2[i][m-j+1]=grid[i][j]; } if(mx==mn)return cout<<0,0; mxrange=mx-mn; int ra=mx-mn; ra=min(ra,solvemain()); swap(grid,grid2); ra=min(ra,solvemain()); //put max on left comp and left comp is decreasing cout<<ra; return 0; } /* greedy idea?: we dont want the min and max value to be in the same component if we cant make the min and max not in the same comp the answer would just be max-min so we will try seperating them this will create a boundary line (depending on max is on the left or right comp) when we have boundary line when can then greedy sort value by the contribution to the answer? so sort by min(max-x,x-min) then we greedy if its really close to max then we will try putting it in max comp which will also shape a new boundary then we keep repeating this? if we cant put it into the respective comp then answer is abs(min/max-x)? will this work?????? */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...