oj.uz

Submission #979002

# Submission time Handle Problem Language Result Execution time Memory
979002 2024-05-10T05:44:49 Z 8pete8 The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 1512 ms 135144 KB 
#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??????
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31832 KB Output is correct
2 Correct 15 ms 31836 KB Output is correct
3 Correct 12 ms 31836 KB Output is correct
4 Correct 13 ms 31836 KB Output is correct
5 Correct 13 ms 31604 KB Output is correct
6 Correct 13 ms 31836 KB Output is correct
7 Correct 13 ms 31836 KB Output is correct
8 Correct 13 ms 31760 KB Output is correct
9 Correct 13 ms 31728 KB Output is correct
10 Correct 14 ms 31836 KB Output is correct
11 Correct 14 ms 31768 KB Output is correct
12 Correct 16 ms 31836 KB Output is correct
13 Correct 18 ms 31832 KB Output is correct
14 Correct 14 ms 31656 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31832 KB Output is correct
2 Correct 15 ms 31836 KB Output is correct
3 Correct 12 ms 31836 KB Output is correct
4 Correct 13 ms 31836 KB Output is correct
5 Correct 13 ms 31604 KB Output is correct
6 Correct 13 ms 31836 KB Output is correct
7 Correct 13 ms 31836 KB Output is correct
8 Correct 13 ms 31760 KB Output is correct
9 Correct 13 ms 31728 KB Output is correct
10 Correct 14 ms 31836 KB Output is correct
11 Correct 14 ms 31768 KB Output is correct
12 Correct 16 ms 31836 KB Output is correct
13 Correct 18 ms 31832 KB Output is correct
14 Correct 14 ms 31656 KB Output is correct
15 Correct 13 ms 31836 KB Output is correct
16 Correct 15 ms 31824 KB Output is correct
17 Correct 25 ms 33240 KB Output is correct
18 Correct 24 ms 33196 KB Output is correct
19 Correct 25 ms 33176 KB Output is correct
20 Correct 23 ms 33292 KB Output is correct
21 Correct 26 ms 33444 KB Output is correct
22 Correct 29 ms 33280 KB Output is correct
23 Correct 29 ms 33452 KB Output is correct
24 Correct 23 ms 33360 KB Output is correct
25 Correct 24 ms 33224 KB Output is correct
26 Correct 29 ms 33440 KB Output is correct
27 Correct 29 ms 33440 KB Output is correct
28 Correct 24 ms 33440 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31832 KB Output is correct
2 Correct 15 ms 31836 KB Output is correct
3 Correct 12 ms 31836 KB Output is correct
4 Correct 13 ms 31836 KB Output is correct
5 Correct 13 ms 31604 KB Output is correct
6 Correct 13 ms 31836 KB Output is correct
7 Correct 13 ms 31836 KB Output is correct
8 Correct 13 ms 31760 KB Output is correct
9 Correct 13 ms 31728 KB Output is correct
10 Correct 14 ms 31836 KB Output is correct
11 Correct 14 ms 31768 KB Output is correct
12 Correct 16 ms 31836 KB Output is correct
13 Correct 18 ms 31832 KB Output is correct
14 Correct 14 ms 31656 KB Output is correct
15 Correct 13 ms 31836 KB Output is correct
16 Correct 15 ms 31824 KB Output is correct
17 Correct 25 ms 33240 KB Output is correct
18 Correct 24 ms 33196 KB Output is correct
19 Correct 25 ms 33176 KB Output is correct
20 Correct 23 ms 33292 KB Output is correct
21 Correct 26 ms 33444 KB Output is correct
22 Correct 29 ms 33280 KB Output is correct
23 Correct 29 ms 33452 KB Output is correct
24 Correct 23 ms 33360 KB Output is correct
25 Correct 24 ms 33224 KB Output is correct
26 Correct 29 ms 33440 KB Output is correct
27 Correct 29 ms 33440 KB Output is correct
28 Correct 24 ms 33440 KB Output is correct
29 Correct 683 ms 93368 KB Output is correct
30 Correct 669 ms 92584 KB Output is correct
31 Correct 777 ms 95100 KB Output is correct
32 Correct 700 ms 94328 KB Output is correct
33 Correct 708 ms 91272 KB Output is correct
34 Correct 735 ms 94320 KB Output is correct
35 Correct 1463 ms 135032 KB Output is correct
36 Correct 1432 ms 130408 KB Output is correct
37 Correct 1512 ms 135144 KB Output is correct