Submission #1114003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114003		Dan4Life	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	22 ms	16208 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int N = (int)2e3+10;
int n, m, a[N][N], b[N][N];

bool chk(int R){
	memset(b,0,sizeof(b));
	int mn = (int)1e9, mx = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			mn = min(mn, a[i][j]), mx = max(mx, a[i][j]);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			b[i][j]=(a[i][j]>mn+R?2:a[i][j]<mx-R);
	bool ok = 1;
	for(int _ = 0; _ < 100; _++){
		for(int i = 0; i < n and ok; i++){
			for(int k : {1,2}){
				int first=-1, last=-1;
				for(int j = 0; j < m; j++){
					if(b[i][j]==k){
						if(first==-1)first=j;
						last=j;
					}
				}
				if(first==last)continue;
				for(int j = first; j <= last; j++){
					ok&=(!b[i][j] or b[i][j]==k);
					b[i][j] = k;
				}
			}
		}
		for(int j = 0; j < m and ok; j++){
			for(int k : {1,2}){
				int first=-1, last=-1;
				for(int i = 0; i < n; i++){
					if(b[i][j]==k){
						if(first==-1)first=i;
						last=i;
					}
				}
				if(first==last)continue;
				for(int i = first; i <= last; i++){
					ok&=(!b[i][j] or b[i][j]==k);
					b[i][j] = k;
				}
			}
		}
		for(int i = 0; i < n; i++){
			int first1 = -1, first2=-1;
			for(int j = 0; j < m; j++){
				if(!b[i][j]) continue;
				if(b[i][j]==1) if(first1==-1) first1=j;
				if(b[i][j]==2) if(first2==-1) first2=j;
			}
			if(first1==-1 or first2==-1) continue;
			for(int j = 0; j < min(first1,first2); j++)
				b[i][j] = (first1<first2?1:2);
			int last1, last2;
			for(int j = 0; j < m; j++){
				if(!b[i][j]) continue;
				if(b[i][j]==1) last1=j;
				if(b[i][j]==2) last2=j;
			}
			for(int j = max(last1,last2)+1; j < m; j++)
				b[i][j] = (last1>last2?1:2);
		}
		for(int j = 0; j < m; j++){
			int first1 = -1, first2=-1;
			for(int i = 0; i < n; i++){
				if(!b[i][j]) continue;
				if(b[i][j]==1) if(first1==-1) first1=i;
				if(b[i][j]==2) if(first2==-1) first2=i;
			}
			if(first1==-1 or first2==-1) continue;
			for(int i = 0; i < min(first1,first2); i++)
				b[i][j] = (first1<first2?1:2);
			int last1, last2;
			for(int i = 0; i < n; i++){
				if(!b[i][j]) continue;
				if(b[i][j]==1) last1=i;
				if(b[i][j]==2) last2=i;
			}
			for(int i = max(last1,last2)+1; i < n; i++)
				b[i][j] = (last1>last2?1:2);
		}
	}
	return ok;
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> a[i][j];
	int l = 0, r = (int)1e9;
	while(l<r){
		int mid = (l+r)/2;
		if(chk(mid)) r=mid;
		else l=mid+1;
	}
	cout << l << "\n";
}

Compilation message (stderr)

joioi.cpp: In function 'bool chk(int)':
joioi.cpp:81:15: warning: 'last2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |    int last1, last2;
      |               ^~~~~
joioi.cpp:81:8: warning: 'last1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |    int last1, last2;
      |        ^~~~~
joioi.cpp:62:15: warning: 'last2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |    int last1, last2;
      |               ^~~~~
joioi.cpp:62:8: warning: 'last1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |    int last1, last2;
      |        ^~~~~

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