Submission #978962

#	Time	Username	Problem	Language	Result	Execution time	Memory
978962		8pete8	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	27 ms	63324 KiB

joioi

#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=1e18,minf=-1e18,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));
	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
		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{
			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 tho
			}
			//left
		}
	}
}
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]=1,mxbound[i]=m+1;
	for(auto i:mxpos)bound[i.f]=max(bound[i.f],i.s),have[i.f]=1;//can be any less
	//there are 2 type of bound decreasing and increasing?
	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]=1,mxbound[i]=m+1;
	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);
	if(valid)ans=min(ans,solve(1));
	return ans;
}
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 can make the min and max not in the same comp the answer would just be max-min
so we will try sperating 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??????
*/

Compilation message (stderr)

joioi.cpp: In function 'long long int solve(long long int)':
joioi.cpp:47:23: warning: control reaches end of non-void function [-Wreturn-type]
   47 |  vector<pair<int,pii>>v;
      |                       ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40