Submission #73776

#	Time	Username	Problem	Language	Result	Execution time	Memory
73776		KLPP	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3623 ms	209992 KiB

joioi

#include<iostream>
#include<stdio.h>

using namespace std;
int h,w;
int A[2000][2000];
int M,m;
bool test(int x){//cout<<x<<endl;
	int region[h][w];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++)region[i][j]=-1;
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(A[i][j]>m+x){
				if(region[i][j]==-1)region[i][j]=1;
				else return false;
			}
			if(A[i][j]<M-x){
				if(region[i][j]==-1)region[i][j]=0;
				else return false;
			}//cout<<region[i][j]<<" ";
		}
	}
	/*for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout<<region[i][j]<<" ";
		}cout<<endl;
	}cout<<endl;*/
	int loH[h+w][2];
	int hiH[h+w][2];
	//compute hi
	for(int i=0;i<h;i++){
		hiH[i][0]=-1;
		hiH[i][1]=-1;
		for(int j=0;j<w;j++){
			if(region[i][j]==0)hiH[i][0]=j;
			if(region[i][j]==1)hiH[i][1]=j;
		}
		//cout<<hiH[i][0]<<" "<<hiH[i][1]<<endl;
	}
	//compute lo
	for(int i=0;i<h;i++){
		loH[i][0]=w;
		loH[i][1]=w;
		for(int j=w-1;j>-1;j--){
			if(region[i][j]==0)loH[i][0]=j;
			if(region[i][j]==1)loH[i][1]=j;
		}
		//cout<<loH[i][0]<<" "<<loH[i][1]<<endl;
	}
	int Hi;
	bool b;
	Hi=-1;
	b=true;
	for(int i=0;i<h;i++){
		Hi=max(Hi,hiH[i][0]);
		if(Hi>=loH[i][1])b=false;
	}
	if(b)return true;
	b=true;
	Hi=-1;
	for(int i=0;i<h;i++){
		Hi=max(Hi,hiH[i][1]);
		if(Hi>=loH[i][0])b=false;
	}
	if(b)return true;
	Hi=-1;
	b=true;
	for(int i=h-1;i>-1;i--){
		Hi=max(Hi,hiH[i][0]);
		if(Hi>=loH[i][1])b=false;
	}
	if(b)return true;
	b=true;
	Hi=-1;
	for(int i=h-1;i>-1;i--){
		Hi=max(Hi,hiH[i][1]);
		if(Hi>=loH[i][0])b=false;
	}
	if(b)return true;
	//compute hi
	for(int i=0;i<w;i++){
		hiH[i][0]=-1;
		hiH[i][1]=-1;
		for(int j=0;j<h;j++){
			if(region[j][i]==0)hiH[i][0]=j;
			if(region[j][i]==1)hiH[i][1]=j;
		}
	}
	//compute lo
	for(int i=0;i<w;i++){
		loH[i][0]=h;
		loH[i][1]=h;
		for(int j=h-1;j>-1;j--){
			if(region[j][i]==0)loH[i][0]=j;
			if(region[j][i]==1)loH[i][1]=j;
		}
	}
	Hi=-1;
	b=true;
	for(int i=0;i<w;i++){
		Hi=max(Hi,hiH[i][0]);
		if(Hi>=loH[i][1])b=false;
	}
	if(b)return true;
	b=true;
	Hi=-1;
	for(int i=0;i<w;i++){
		Hi=max(Hi,hiH[i][1]);
		if(Hi>=loH[i][0])b=false;
	}
	if(b)return true;
	Hi=-1;
	b=true;
	for(int i=w-1;i>-1;i--){
		Hi=max(Hi,hiH[i][0]);
		if(Hi>=loH[i][1])b=false;
	}
	if(b)return true;
	b=true;
	Hi=-1;
	for(int i=w-1;i>-1;i--){
		Hi=max(Hi,hiH[i][1]);
		if(Hi>=loH[i][0])b=false;
	}
	if(b)return true;
	
	return false;
}
int main(){
	scanf("%d %d",&h,&w);
	M=-1;
	m=1000000001;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			scanf("%d",&A[i][j]);
			M=max(M,A[i][j]);
			m=min(m,A[i][j]);
		}
	}
	int hi,lo;
	lo=-1;
	hi=M-m;
	while(hi-lo>1){
		int mid=(hi+lo)/2;
		bool b=test(mid);
		if(b)hi=mid;
		else lo=mid;
	}printf("%d",hi);
	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&h,&w);
  ~~~~~^~~~~~~~~~~~~~~
joioi.cpp:137:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&A[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

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