Submission #228000

#	Time	Username	Problem	Language	Result	Execution time	Memory
228000		dvdg6566	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3172 ms	81052 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 2010;
const ll INF = 1e18;
const ll MOD = 1e9+7;

ll N,M;
ll A[MAXN][MAXN];
ll LOW, UPP;
int B[MAXN][MAXN];
pi ones[MAXN], twos[MAXN];

bool ask(){
	ll L=0;
	// for (int i=1;i<=N;++i){for(int j=1;j<=M;++j)cout<<B[i][j]<<' ';cout<<'\n';}
	for(int i=1;i<=N;++i){
		ones[i]=mp(INF,0);
		twos[i]=mp(INF,0);
		for(ll j=1;j<=M;++j){
			if(B[i][j]==1){
				ones[i].f=min(ones[i].f,j);
				ones[i].s=max(ones[i].s,j);
			}else if(B[i][j]==2){
				twos[i].f=min(twos[i].f,j);
				twos[i].s=max(twos[i].s,j);
			}
		}
		if(ones[i].f!=INF){
			L=max(L,ones[i].s);
		}
		if (twos[i].f!=INF&&twos[i].f<=L)return 0;
		// cout<<ones[i].f<<' '<<ones[i].s<<'\n';
		// cout<<twos[i].f<<' '<<twos[i].s<<'\n';
	}
	return 1;
}

bool works(int L){
	pi a = mp(LOW,LOW+L);
	pi b = mp(UPP-L,UPP);
	for(int i=1;i<=N;++i)for(int j=1;j<=M;++j){
		if(A[i][j]<b.f&&A[i][j]>a.s)return 0;
		if(A[i][j]<b.f)B[i][j]=1;
		else if(A[i][j]>a.s)B[i][j]=2;
		else B[i][j]=0;
	}
	for(int rep=0;rep<4;++rep){
		int t=ask();
		if(t)return 1;
		if (rep==0||rep==2){
			// flip hori
			for (int i=1;i<=N;++i)for (int j=1;j+j<=M;++j){
				swap(B[i][j], B[i][M+1-j]);
			}
		}else{
			for (int i=1;i+i<=N;++i)for(int j=1;j<=M;++j){
				swap(B[i][j], B[N+1-i][j]);
			}
		}
		// break;
	}
	return 0;
}

int main(){
	cin>>N>>M;
	LOW=INF;
	for (int i=1;i<=N;++i)for(int j=1;j<=M;++j){
		cin>>A[i][j];
		UPP=max(UPP,A[i][j]);
		LOW=min(LOW,A[i][j]);
	}
	
	ll lb=0;
	ll ub=UPP-LOW+1;
	while(ub>lb){
		int mid=(lb+ub)/2;
		// cerr<<mid<<'\n';
		if(works(mid))ub=mid;
		else lb=mid+1;
	}
	cout<<lb;
}

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