답안 #65419 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65419	2018-08-07T14:36:15 Z	keko37	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3708 ms	34664 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	8312 KB	Output is correct
2	Correct	25 ms	8416 KB	Output is correct
3	Correct	35 ms	8488 KB	Output is correct
4	Correct	28 ms	8488 KB	Output is correct
5	Correct	27 ms	8488 KB	Output is correct
6	Correct	26 ms	8488 KB	Output is correct
7	Correct	36 ms	8488 KB	Output is correct
8	Correct	32 ms	8512 KB	Output is correct
9	Correct	33 ms	8552 KB	Output is correct
10	Correct	29 ms	8552 KB	Output is correct
11	Correct	31 ms	8552 KB	Output is correct
12	Correct	25 ms	8552 KB	Output is correct
13	Correct	28 ms	8552 KB	Output is correct
14	Correct	27 ms	8552 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	8312 KB	Output is correct
2	Correct	25 ms	8416 KB	Output is correct
3	Correct	35 ms	8488 KB	Output is correct
4	Correct	28 ms	8488 KB	Output is correct
5	Correct	27 ms	8488 KB	Output is correct
6	Correct	26 ms	8488 KB	Output is correct
7	Correct	36 ms	8488 KB	Output is correct
8	Correct	32 ms	8512 KB	Output is correct
9	Correct	33 ms	8552 KB	Output is correct
10	Correct	29 ms	8552 KB	Output is correct
11	Correct	31 ms	8552 KB	Output is correct
12	Correct	25 ms	8552 KB	Output is correct
13	Correct	28 ms	8552 KB	Output is correct
14	Correct	27 ms	8552 KB	Output is correct
15	Correct	27 ms	8552 KB	Output is correct
16	Correct	40 ms	9516 KB	Output is correct
17	Correct	71 ms	9720 KB	Output is correct
18	Correct	53 ms	10120 KB	Output is correct
19	Correct	57 ms	10388 KB	Output is correct
20	Correct	59 ms	10404 KB	Output is correct
21	Correct	86 ms	10900 KB	Output is correct
22	Correct	58 ms	11416 KB	Output is correct
23	Correct	67 ms	11672 KB	Output is correct
24	Correct	56 ms	12060 KB	Output is correct
25	Correct	83 ms	12404 KB	Output is correct
26	Correct	79 ms	12976 KB	Output is correct
27	Correct	65 ms	13184 KB	Output is correct
28	Correct	76 ms	13696 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	8312 KB	Output is correct
2	Correct	25 ms	8416 KB	Output is correct
3	Correct	35 ms	8488 KB	Output is correct
4	Correct	28 ms	8488 KB	Output is correct
5	Correct	27 ms	8488 KB	Output is correct
6	Correct	26 ms	8488 KB	Output is correct
7	Correct	36 ms	8488 KB	Output is correct
8	Correct	32 ms	8512 KB	Output is correct
9	Correct	33 ms	8552 KB	Output is correct
10	Correct	29 ms	8552 KB	Output is correct
11	Correct	31 ms	8552 KB	Output is correct
12	Correct	25 ms	8552 KB	Output is correct
13	Correct	28 ms	8552 KB	Output is correct
14	Correct	27 ms	8552 KB	Output is correct
15	Correct	27 ms	8552 KB	Output is correct
16	Correct	40 ms	9516 KB	Output is correct
17	Correct	71 ms	9720 KB	Output is correct
18	Correct	53 ms	10120 KB	Output is correct
19	Correct	57 ms	10388 KB	Output is correct
20	Correct	59 ms	10404 KB	Output is correct
21	Correct	86 ms	10900 KB	Output is correct
22	Correct	58 ms	11416 KB	Output is correct
23	Correct	67 ms	11672 KB	Output is correct
24	Correct	56 ms	12060 KB	Output is correct
25	Correct	83 ms	12404 KB	Output is correct
26	Correct	79 ms	12976 KB	Output is correct
27	Correct	65 ms	13184 KB	Output is correct
28	Correct	76 ms	13696 KB	Output is correct
29	Correct	2393 ms	33936 KB	Output is correct
30	Correct	2427 ms	34356 KB	Output is correct
31	Correct	2644 ms	34664 KB	Output is correct
32	Correct	2271 ms	34664 KB	Output is correct
33	Correct	1943 ms	34664 KB	Output is correct
34	Correct	2567 ms	34664 KB	Output is correct
35	Correct	3423 ms	34664 KB	Output is correct
36	Correct	2781 ms	34664 KB	Output is correct
37	Correct	3708 ms	34664 KB	Output is correct

답안 #65419

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