답안 #62254 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62254	2018-07-28T00:22:13 Z	kingpig9	The Kingdom of JOIOI (JOI17_joioi)	C++11	100 / 100	3104 ms	52860 KB

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

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.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	576 KB	Output is correct
3	Correct	3 ms	576 KB	Output is correct
4	Correct	3 ms	632 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	820 KB	Output is correct
8	Correct	3 ms	820 KB	Output is correct
9	Correct	3 ms	820 KB	Output is correct
10	Correct	3 ms	820 KB	Output is correct
11	Correct	3 ms	820 KB	Output is correct
12	Correct	4 ms	820 KB	Output is correct
13	Correct	2 ms	820 KB	Output is correct
14	Correct	3 ms	820 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	576 KB	Output is correct
3	Correct	3 ms	576 KB	Output is correct
4	Correct	3 ms	632 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	820 KB	Output is correct
8	Correct	3 ms	820 KB	Output is correct
9	Correct	3 ms	820 KB	Output is correct
10	Correct	3 ms	820 KB	Output is correct
11	Correct	3 ms	820 KB	Output is correct
12	Correct	4 ms	820 KB	Output is correct
13	Correct	2 ms	820 KB	Output is correct
14	Correct	3 ms	820 KB	Output is correct
15	Correct	3 ms	820 KB	Output is correct
16	Correct	11 ms	2604 KB	Output is correct
17	Correct	19 ms	2936 KB	Output is correct
18	Correct	13 ms	3316 KB	Output is correct
19	Correct	26 ms	3584 KB	Output is correct
20	Correct	21 ms	3584 KB	Output is correct
21	Correct	22 ms	4116 KB	Output is correct
22	Correct	20 ms	4376 KB	Output is correct
23	Correct	32 ms	4888 KB	Output is correct
24	Correct	15 ms	4892 KB	Output is correct
25	Correct	33 ms	5620 KB	Output is correct
26	Correct	30 ms	6008 KB	Output is correct
27	Correct	25 ms	6396 KB	Output is correct
28	Correct	19 ms	6784 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	576 KB	Output is correct
3	Correct	3 ms	576 KB	Output is correct
4	Correct	3 ms	632 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	820 KB	Output is correct
8	Correct	3 ms	820 KB	Output is correct
9	Correct	3 ms	820 KB	Output is correct
10	Correct	3 ms	820 KB	Output is correct
11	Correct	3 ms	820 KB	Output is correct
12	Correct	4 ms	820 KB	Output is correct
13	Correct	2 ms	820 KB	Output is correct
14	Correct	3 ms	820 KB	Output is correct
15	Correct	3 ms	820 KB	Output is correct
16	Correct	11 ms	2604 KB	Output is correct
17	Correct	19 ms	2936 KB	Output is correct
18	Correct	13 ms	3316 KB	Output is correct
19	Correct	26 ms	3584 KB	Output is correct
20	Correct	21 ms	3584 KB	Output is correct
21	Correct	22 ms	4116 KB	Output is correct
22	Correct	20 ms	4376 KB	Output is correct
23	Correct	32 ms	4888 KB	Output is correct
24	Correct	15 ms	4892 KB	Output is correct
25	Correct	33 ms	5620 KB	Output is correct
26	Correct	30 ms	6008 KB	Output is correct
27	Correct	25 ms	6396 KB	Output is correct
28	Correct	19 ms	6784 KB	Output is correct
29	Correct	1553 ms	51164 KB	Output is correct
30	Correct	1757 ms	52724 KB	Output is correct
31	Correct	1762 ms	52724 KB	Output is correct
32	Correct	1223 ms	52760 KB	Output is correct
33	Correct	794 ms	52760 KB	Output is correct
34	Correct	1880 ms	52852 KB	Output is correct
35	Correct	1644 ms	52852 KB	Output is correct
36	Correct	1171 ms	52852 KB	Output is correct
37	Correct	3104 ms	52860 KB	Output is correct

답안 #62254

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0