Submission #65419

#	Time	Username	Problem	Language	Result	Execution time	Memory
65419		keko37	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3708 ms	34664 KiB

joioi

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAXN = 2005;
const int INF = 1000000007;

int n, m, mn = INF, mx, rev;
int l[MAXN] [MAXN];
short c[MAXN] [MAXN];

bool oboji (int d) {
	for (int s=0; s<m; s++) {
		if (d == 1) {
			for (int r=1; r<n; r++) {
				if (c[r-1] [s] == 1) {
					if (c[r] [s] == 2) return 0;
					c[r] [s] = 1;
				}
			}
		} else {
			for (int r=n-2; r>=0; r--) {
				if (c[r+1] [s] == 1) {
					if (c[r] [s] == 2) return 0;
					c[r] [s] = 1;
				}
			}
		}
	}
	for (int r=0; r<n; r++) {
		for (int s=m-2; s>=0; s--) {
			if (c[r] [s+1] == 1) {
				if (c[r] [s] == 2) return 0;
				c[r] [s] = 1;
			}
		}
	}
	return 1;
}

bool ok (int x) {
	memset(c, 0, sizeof c);
	int lef = MAXN, rig = -1, hlef, hrig;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			if (l[i] [j] > mn + x) {
				c[i] [j] = 2;
				if (j < lef) {
					lef = j;
					hlef = i;
				}
			}
			if (l[i] [j] < mx - x) {
				if (c[i] [j] == 2) return 0;
				c[i] [j] = 1;
				if (j > rig) {
					rig = j;
					hrig = i;
				}
			}
		}
	}
	if (rig < lef) return 1;
	if (hlef < hrig) return oboji(1); return oboji(2);
}

bool moze (int x) {
	if (!rev) {
		if (ok(x)) return 1;
		for (int i=0; i<n; i++) {
			reverse(l[i], l[i]+m);
		}
		if (ok(x)) {
			rev = 1;
			return 1;
		} else {
			return 0;
		}
	}
	return ok(x);
}

int main () {
	cin >> n >> m;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> l[i] [j];
			mn = min(mn, l[i] [j]);
			mx = max(mx, l[i] [j]);
		}
	}
	int low = 0, high = INF, mid;
	while (low < high) {
		mid = (low+high) / 2;
		if (moze(mid)) {
			high = mid;
		} else {
			low = mid+1;
		}
	}
	cout << low;
	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'bool ok(int)':
joioi.cpp:66:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (hlef < hrig) return oboji(1); return oboji(2);
  ^~
joioi.cpp:66:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (hlef < hrig) return oboji(1); return oboji(2);
                                    ^~~~~~
joioi.cpp:66:2: warning: 'hrig' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (hlef < hrig) return oboji(1); return oboji(2);
  ^~
joioi.cpp:66:2: warning: 'hlef' may be used uninitialized in this function [-Wmaybe-uninitialized]

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