oj.uz

답안 #227952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
227952 2020-04-29T10:51:53 Z dvdg6566 The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 5 ms 384 KB 
#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<=N;++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<=M;++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;
		if(works(mid))ub=mid;
		else lb=mid+1;
	}
	cout<<lb;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -