Submission #62254

#	Time	Username	Problem	Language	Result	Execution time	Memory
62254		kingpig9	The Kingdom of JOIOI (JOI17_joioi)	C++11	100 / 100	3104 ms	52860 KiB

joioi

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2010;

void setmin (int &a, int b) {
	if (a > b) {
		a = b;
	}
}

void setmax (int &a, int b) {
	if (a < b) {
		a = b;
	}
}

int N, M, mx = 0, mn = 1e9;
int A[MAXN][MAXN];
int msk[MAXN][MAXN];
int mnpos[2][MAXN], mxpos[2][MAXN];	//min position for each of them

void calcpos() {
	for (int i = 1; i <= N; i++) {
		mnpos[0][i] = mnpos[1][i] = M + 1;
		mxpos[0][i] = mxpos[1][i] = 0;
		for (int j = 1; j <= M; j++) {
			for (int k = 0; k < 2; k++) {
				if (msk[i][j] == (1 << k)) {
					setmin(mnpos[k][i], j);
					setmax(mxpos[k][i], j);
				}
			}
		}
	}
}

bool solve (int b) {
	//can the bit b be monotonically increasing??
	int cur = 0;

	for (int i = 1; i <= N; i++) {
		if (mxpos[b][i] > mnpos[b ^ 1][i]) {
			return false;
		}

		//so can take mxpos[b][i] <= j < mnpos[b ^ 1][i]
		if (cur >= mnpos[b ^ 1][i]) {
			return false;
		}

		setmax(cur, mxpos[b][i]);
	}

	return true;
}

bool moo (int g) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			msk[i][j] = 0;
			if (A[i][j] <= mn + g) {
				msk[i][j] ^= 1;
			}
			if (A[i][j] >= mx - g) {
				msk[i][j] ^= 2;
			}

			if (msk[i][j] == 0) {
				return false;
			}
		}
	}

	calcpos();
	if (solve(0) || solve(1)) {
		return true;
	}

	//check if it can be decreasing or increasing!
	for (int i = 1; i <= N; i++) {
		reverse(msk[i] + 1, msk[i] + M + 1);
	}

	calcpos();
	if (solve(0) || solve(1)) {
		return true;
	}
	return false;
}

int main() {
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%d", &A[i][j]);
			setmin(mn, A[i][j]);
			setmax(mx, A[i][j]);
		}
	}

	int lo = -1, hi = mx - mn;
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		if (moo(mid)) {
			hi = mid;
		} else {
			lo = mid;
		}
	}

	printf("%d\n", hi);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp:97: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