oj.uz

답안 #62253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62253 2018-07-28T00:21:10 Z kingpig9 The Kingdom of JOIOI (JOI17_joioi) C++11
60 / 100
 2808 ms 263168 KB 
#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 400 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 3 ms 696 KB Output is correct
11 Correct 3 ms 696 KB Output is correct
12 Correct 3 ms 696 KB Output is correct
13 Correct 3 ms 696 KB Output is correct
14 Correct 3 ms 696 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 3 ms 696 KB Output is correct
11 Correct 3 ms 696 KB Output is correct
12 Correct 3 ms 696 KB Output is correct
13 Correct 3 ms 696 KB Output is correct
14 Correct 3 ms 696 KB Output is correct
15 Correct 4 ms 780 KB Output is correct
16 Correct 13 ms 2708 KB Output is correct
17 Correct 18 ms 2868 KB Output is correct
18 Correct 17 ms 3224 KB Output is correct
19 Correct 31 ms 3508 KB Output is correct
20 Correct 21 ms 3540 KB Output is correct
21 Correct 21 ms 4164 KB Output is correct
22 Correct 19 ms 4552 KB Output is correct
23 Correct 27 ms 4960 KB Output is correct
24 Correct 15 ms 4980 KB Output is correct
25 Correct 38 ms 5684 KB Output is correct
26 Correct 23 ms 6072 KB Output is correct
27 Correct 22 ms 6460 KB Output is correct
28 Correct 21 ms 6848 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 3 ms 696 KB Output is correct
11 Correct 3 ms 696 KB Output is correct
12 Correct 3 ms 696 KB Output is correct
13 Correct 3 ms 696 KB Output is correct
14 Correct 3 ms 696 KB Output is correct
15 Correct 4 ms 780 KB Output is correct
16 Correct 13 ms 2708 KB Output is correct
17 Correct 18 ms 2868 KB Output is correct
18 Correct 17 ms 3224 KB Output is correct
19 Correct 31 ms 3508 KB Output is correct
20 Correct 21 ms 3540 KB Output is correct
21 Correct 21 ms 4164 KB Output is correct
22 Correct 19 ms 4552 KB Output is correct
23 Correct 27 ms 4960 KB Output is correct
24 Correct 15 ms 4980 KB Output is correct
25 Correct 38 ms 5684 KB Output is correct
26 Correct 23 ms 6072 KB Output is correct
27 Correct 22 ms 6460 KB Output is correct
28 Correct 21 ms 6848 KB Output is correct
29 Correct 1506 ms 56864 KB Output is correct
30 Correct 1613 ms 80232 KB Output is correct
31 Correct 1953 ms 103220 KB Output is correct
32 Correct 1419 ms 126344 KB Output is correct
33 Correct 678 ms 142696 KB Output is correct
34 Correct 1983 ms 169604 KB Output is correct
35 Correct 1602 ms 208296 KB Output is correct
36 Correct 968 ms 241992 KB Output is correct
37 Runtime error 2808 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.