Submission #954203

#	Time	Username	Problem	Language	Result	Execution time	Memory
954203		StefanSebez	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	0 ms	348 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;scanf("%i%i",&n,&m);
    int a[n+10][m+10],mn=1e9+50,maks=0;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {scanf("%i",&a[i][j]);mn=min(mn,a[i][j]),maks=max(maks,a[i][j]);}
    int l=1,r=maks-mn-1,res=maks-mn;
    while(l<=r){
		//printf("%i %i\n",l,r);
		int mid=l+(r-l)/2;
		int b[n+10][m+10];
		memset(b,0,sizeof(b));
		bool bul=false;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(a[i][j]>mn+mid) b[i][j]=2;
				if(a[i][j]<maks-mid) b[i][j]=1;
				if(mn+mid<a[i][j] && a[i][j]<maks-mid) bul=true;
			}
		}
		if(bul) {l=mid+1;continue;}
		while(1){
			int c[n+50][m+50];
			for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) c[i][j]=b[i][j];
			bool bul2=false;
			for(int i=1;i<=n;i++){
				int L1=-1,R1=-1,L2=-1,R2=-1;
				for(int j=1;j<=m;j++){
					if(b[i][j]==1) R1=j;
					if(b[i][j]==2) R2=j;
				}
				for(int j=m;j>=1;j--){
					if(b[i][j]==1) L1=j;
					if(b[i][j]==2) L2=j;
				}
				if(L1==-1 || L2==-1) continue;
				//bul2=true;
				if((L1<L2 && L2<R1) || (L1<R2 && R2<R1) || (L2<L1 && L1<R2) || (L2<R1 && R1<R2)) {bul=true;break;}
				if(R1<L2){
					for(int j=1;j<=R1;j++) b[i][j]=1;
					for(int j=L2;j<=m;j++) b[i][j]=2;
				}
				else{
					for(int j=1;j<=R2;j++) b[i][j]=2;
					for(int j=L1;j<=m;j++) b[i][j]=1;
				}
			}
			for(int j=1;j<=m;j++){
				int L1=-1,R1=-1,L2=-1,R2=-1;
				for(int i=1;i<=n;i++){
					if(b[i][j]==1) R1=i;
					if(b[i][j]==2) R2=i;
				}
				for(int i=n;i>=1;i--){
					if(b[i][j]==1) L1=i;
					if(b[i][j]==2) L2=i;
				}
				if(L1==-1 || L2==-1) continue;
				//bul2=true;
				if((L1<L2 && L2<R1) || (L1<R2 && R2<R1) || (L2<L1 && L1<R2) || (L2<R1 && R1<R2)) {bul=true;break;}
				if(R1<L2){
					for(int i=1;i<=R1;i++) b[i][j]=1;
					for(int i=L2;i<=n;i++) b[i][j]=2;
				}
				else{
					for(int i=1;i<=R2;i++) b[i][j]=2;
					for(int i=L1;i<=n;i++) b[i][j]=1;
				}
			}
			for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(b[i][j]!=c[i][j]) bul2=true;
			if(!bul2) break;
		}
		if(bul) l=mid+1;
		else r=mid-1,res=mid;
    }
    printf("%i\n",res);
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:5:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |     int n,m;scanf("%i%i",&n,&m);
      |             ~~~~~^~~~~~~~~~~~~~
joioi.cpp:6:90: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     int a[n+10][m+10],mn=1e9+50,maks=0;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {scanf("%i",&a[i][j]);mn=min(mn,a[i][j]),maks=max(maks,a[i][j]);}
      |                                                                                     ~~~~~^~~~~~~~~~~~~~~

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