oj.uz

Submission #889112

# Submission time Handle Problem Language Result Execution time Memory
889112 2023-12-18T22:52:53 Z rainboy World of Tank (innopolis2018_final_E) C
30 / 100
 110 ms 69016 KB 
/* https://codeforces.com/blog/entry/58056 */
#include <stdio.h>
#include <string.h>

#define N	2000001

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int xx1[N], xx2[N], xx[N], bb[N], n, t;

int dp[N * 2], pp[N * 2];

void update(int u, int v, int x) {
	if (dp[v] < x)
		dp[v] = x, pp[v] = u;
}

int xx_[N], m;
int yy1[N], k;

int trace(int u) {
	int i, x, y;

	if (u == (0 << 1 | 0))
		return t;
	i = u >> 1, y = u & 1;
	x = trace(pp[u]);
	if (pp[u] == (u ^ 1)) {
		xx_[m++] = xx[i];
		x = max(x, xx[i]);
	} else {
		if ((bb[i] & 1 << y) != 0)
			xx1[k] = x, yy1[k] = y + 1, k++, x += t;
	}
	return x;
}

int main() {
	int n1, n2, x_, h, i, i1, i2, u;

	scanf("%d%d%d%d", &x_, &n1, &n2, &t);
	for (i = 0; i < n1; i++)
		scanf("%d", &xx1[i]);
	xx1[n1] = x_ + 1;
	for (i = 0; i < n2; i++)
		scanf("%d", &xx2[i]);
	xx2[n2] = x_ + 1;
	i1 = 0, i2 = 0, n = 0;
	xx[n] = 0, bb[n] = 0, n++;
	while (i1 < n1 || i2 < n2)
		if (xx1[i1] < xx2[i2]) {
			if (xx[n - 1] + 1 < xx1[i1])
				xx[n] = xx[n - 1] + 1, bb[n] = 0, n++;
			xx[n] = xx1[i1], bb[n] = 1, n++;
			i1++;
		} else if (xx1[i1] > xx2[i2]) {
			if (xx[n - 1] + 1 < xx2[i2])
				xx[n] = xx[n - 1] + 1, bb[n] = 0, n++;
			xx[n] = xx2[i2], bb[n] = 2, n++;
			i2++;
		} else {
			if (xx[n - 1] + 1 < xx1[i1])
				xx[n] = xx[n - 1] + 1, bb[n] = 0, n++;
			xx[n] = xx1[i1], bb[n] = 3, n++;
			i1++, i2++;
		}
	memset(dp, -1, n * 2 * sizeof *dp), memset(pp, -1, n * 2 * sizeof *pp), dp[0 << 1 | 0] = 0;
	for (i = 0; i < n; i++) {
		if (dp[i << 1 | 0] != -1 && (bb[i] & 2) == 0)
			update(i << 1 | 0, i << 1 | 1, min(dp[i << 1 | 0], t));
		if (dp[i << 1 | 1] != -1 && (bb[i] & 1) == 0)
			update(i << 1 | 1, i << 1 | 0, min(dp[i << 1 | 1], t));
		if (i + 1 < n) {
			if (dp[i << 1 | 0] != -1) {
				if ((bb[i + 1] & 1) == 0)
					update(i << 1 | 0, i + 1 << 1 | 0, dp[i << 1 | 0] + xx[i + 1] - xx[i]);
				else if (dp[i << 1 | 0] >= t)
					update(i << 1 | 0, i + 1 << 1 | 0, dp[i << 1 | 0] - t + xx[i + 1] - xx[i]);
			}
			if (dp[i << 1 | 1] != -1) {
				if ((bb[i + 1] & 2) == 0)
					update(i << 1 | 1, i + 1 << 1 | 1, dp[i << 1 | 1] + xx[i + 1] - xx[i]);
				else if (dp[i << 1 | 1] >= t)
					update(i << 1 | 1, i + 1 << 1 | 1, dp[i << 1 | 1] - t + xx[i + 1] - xx[i]);
			}
		}
	}
	if (dp[n - 1 << 1 | 0] == -1 && dp[n - 1 << 1 | 1] == -1) {
		printf("No\n");
		return 0;
	}
	u = dp[n - 1 << 1 | 0] != -1 ? n - 1 << 1 | 0 : n - 1 << 1 | 1;
	if (pp[u] == (u ^ 1))
		u ^= 1;
	trace(u);
	printf("Yes\n");
	printf("%d\n", m);
	for (h = 0; h < m; h++)
		printf("%d ", xx_[h]);
	printf("\n");
	printf("%d\n", k);
	for (h = 0; h < k; h++)
		printf("%d %d\n", xx1[h], yy1[h]);
	return 0;
}

Compilation message

E.c: In function 'main':
E.c:77:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |      update(i << 1 | 0, i + 1 << 1 | 0, dp[i << 1 | 0] + xx[i + 1] - xx[i]);
      |                         ~~^~~
E.c:79:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |      update(i << 1 | 0, i + 1 << 1 | 0, dp[i << 1 | 0] - t + xx[i + 1] - xx[i]);
      |                         ~~^~~
E.c:83:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   83 |      update(i << 1 | 1, i + 1 << 1 | 1, dp[i << 1 | 1] + xx[i + 1] - xx[i]);
      |                         ~~^~~
E.c:85:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   85 |      update(i << 1 | 1, i + 1 << 1 | 1, dp[i << 1 | 1] - t + xx[i + 1] - xx[i]);
      |                         ~~^~~
E.c:89:11: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   89 |  if (dp[n - 1 << 1 | 0] == -1 && dp[n - 1 << 1 | 1] == -1) {
      |         ~~^~~
E.c:89:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   89 |  if (dp[n - 1 << 1 | 0] == -1 && dp[n - 1 << 1 | 1] == -1) {
      |                                     ~~^~~
E.c:93:11: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   93 |  u = dp[n - 1 << 1 | 0] != -1 ? n - 1 << 1 | 0 : n - 1 << 1 | 1;
      |         ~~^~~
E.c:93:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   93 |  u = dp[n - 1 << 1 | 0] != -1 ? n - 1 << 1 | 0 : n - 1 << 1 | 1;
      |                                 ~~^~~
E.c:93:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   93 |  u = dp[n - 1 << 1 | 0] != -1 ? n - 1 << 1 | 0 : n - 1 << 1 | 1;
      |                                                  ~~^~~
E.c:42:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d%d%d%d", &x_, &n1, &n2, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
E.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d", &xx1[i]);
      |   ^~~~~~~~~~~~~~~~~~~~
E.c:47:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d", &xx2[i]);
      |   ^~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 2 ms 12720 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 2 ms 12716 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 2 ms 12732 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 2 ms 12888 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 2 ms 12720 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 2 ms 12716 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 2 ms 12732 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 2 ms 12888 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 2 ms 12992 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 2 ms 12632 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB [OK, Yes] n = 20, m1 = 12, m2 = 9, t = 3
2 Incorrect 1 ms 12632 KB [No solution found] n = 10, m1 = 4, m2 = 2, t = 2
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 2 ms 12720 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 2 ms 12716 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 2 ms 12732 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 2 ms 12888 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 2 ms 12992 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 2 ms 12632 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501
24 Correct 2 ms 12632 KB [OK, Yes] n = 500, m1 = 197, m2 = 53, t = 2
25 Correct 1 ms 12740 KB [OK, Yes] n = 500, m1 = 189, m2 = 61, t = 3
26 Correct 2 ms 12636 KB [OK, No] n = 500, m1 = 66, m2 = 184, t = 4
27 Correct 2 ms 12712 KB [OK, Yes] n = 500, m1 = 248, m2 = 252, t = 1
28 Correct 2 ms 12636 KB [OK, Yes] n = 500, m1 = 248, m2 = 252, t = 1
29 Correct 2 ms 12636 KB [OK, Yes] n = 500, m1 = 205, m2 = 295, t = 1
30 Correct 62 ms 47192 KB [OK, Yes] n = 1000000, m1 = 183472, m2 = 66528, t = 7
31 Correct 46 ms 46952 KB [OK, Yes] n = 1000000, m1 = 206211, m2 = 43789, t = 6
32 Correct 43 ms 44940 KB [OK, Yes] n = 1000000, m1 = 229445, m2 = 20555, t = 7
33 Correct 49 ms 34388 KB [OK, No] n = 1000000, m1 = 261335, m2 = 238665, t = 2
34 Correct 89 ms 69016 KB [OK, Yes] n = 1000000, m1 = 374819, m2 = 125181, t = 3
35 Correct 89 ms 66840 KB [OK, Yes] n = 1000000, m1 = 88376, m2 = 411624, t = 3
36 Correct 2 ms 12636 KB [OK, Yes] n = 500, m1 = 125, m2 = 125, t = 2
37 Correct 110 ms 56984 KB [OK, Yes] n = 1000000, m1 = 250000, m2 = 250000, t = 2
38 Correct 38 ms 36192 KB [OK, Yes] n = 1000000, m1 = 94957, m2 = 94938, t = 12
39 Correct 38 ms 37064 KB [OK, Yes] n = 1000000, m1 = 94972, m2 = 95007, t = 10
40 Incorrect 4 ms 12892 KB [No solution found] n = 1000000, m1 = 14064, m2 = 13936, t = 200
41 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 2 ms 12720 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 2 ms 12716 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 2 ms 12636 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 2 ms 12732 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 2 ms 12888 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 2 ms 12892 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 2 ms 12992 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 2 ms 12636 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 2 ms 12632 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501
24 Correct 1 ms 12636 KB [OK, Yes] n = 20, m1 = 12, m2 = 9, t = 3
25 Incorrect 1 ms 12632 KB [No solution found] n = 10, m1 = 4, m2 = 2, t = 2
26 Halted 0 ms 0 KB -