oj.uz

Submission #490940

# Submission time Handle Problem Language Result Execution time Memory
490940 2021-11-29T22:41:54 Z rainboy Segway (COI19_segway) C
100 / 100
 785 ms 888 KB 
#include <stdio.h>
#include <string.h>

#define N	20000
#define X	300
#define T	15000
#define INF	0x3f3f3f3f

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

int main() {
	static int ss[N][3], xx[N], yy[N], tt[N], kk[X + 1], kk_[T + 1];
	static char accel[X + 1];
	int n, m, h, i, x, t;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		for (h = 0; h < 3; h++)
			scanf("%d", &ss[i][h]);
	scanf("%d", &m);
	for (h = 0; h < m; h++) {
		scanf("%d", &x);
		accel[x] = 1;
	}
	if (m == 1) {
		for (i = 0; i < n; i++) {
			if (x <= 100)
				tt[i] = ss[i][0] * x;
			else if (x <= 200)
				tt[i] = ss[i][0] * 100 + ss[i][1] * (x - 100);
			else
				tt[i] = ss[i][0] * 100 + ss[i][1] * 100 + ss[i][2] * (x - 200);
			kk_[tt[i]]++;
		}
		for (t = 1; t <= T; t++)
			kk_[t] += kk_[t - 1];
		for (i = 0; i < n; i++) {
			int k = kk_[tt[i] - 1] % 20;

			if (x + k >= 300)
				tt[i] += 300 - x;
			else if (x + k >= 200)
				tt[i] += k + ss[i][2] * (300 - (x + k));
			else if (x + k >= 100)
				tt[i] += k + ss[i][1] * (200 - (x + k)) + ss[i][2] * 100;
			else
				tt[i] += k + ss[i][0] * (100 - (x + k)) + ss[i][1] * 100 + ss[i][2] * 100;
		}
	} else {
		for (i = 0; i < n; i++)
			tt[i] = ss[i][0];
		while (1) {
			t = INF;
			for (i = 0; i < n; i++)
				if (xx[i] != X)
					t = min(t, tt[i]);
			if (t == INF)
				break;
			for (i = 0; i < n; i++)
				if (xx[i] != X && tt[i] == t) {
					xx[i]++;
					if (xx[i] < X && accel[xx[i]] && yy[i] <= xx[i])
						yy[i] = -1;
				}
			memset(kk, 0, (X + 1) * sizeof *kk);
			for (i = 0; i < n; i++)
				if (tt[i] == t)
					kk[xx[i] - 1]++;
				else
					kk[xx[i]]++;
			for (x = X - 1; x >= 0; x--)
				kk[x] += kk[x + 1];
			for (i = 0; i < n; i++)
				if (yy[i] == -1)
					yy[i] = xx[i] + kk[xx[i]] % 20;
			for (i = 0; i < n; i++)
				if (xx[i] != X && tt[i] == t)
					tt[i] = yy[i] <= xx[i] ? t + ss[i][xx[i] / (X / 3)] : t + 1;
		}
	}
	for (i = 0; i < n; i++)
		printf("%d\n", tt[i]);
	return 0;
}

Compilation message

segway.c: In function 'main':
segway.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
segway.c:19:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |    scanf("%d", &ss[i][h]);
      |    ^~~~~~~~~~~~~~~~~~~~~~
segway.c:20:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
segway.c:22:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d", &x);
      |   ^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 7 ms 716 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 3 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 5 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 7 ms 204 KB Output is correct
8 Correct 9 ms 204 KB Output is correct
9 Correct 9 ms 296 KB Output is correct
10 Correct 16 ms 288 KB Output is correct
11 Correct 6 ms 204 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 3 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 5 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 7 ms 204 KB Output is correct
13 Correct 9 ms 204 KB Output is correct
14 Correct 9 ms 296 KB Output is correct
15 Correct 16 ms 288 KB Output is correct
16 Correct 6 ms 204 KB Output is correct
17 Correct 76 ms 308 KB Output is correct
18 Correct 27 ms 348 KB Output is correct
19 Correct 336 ms 560 KB Output is correct
20 Correct 785 ms 624 KB Output is correct
21 Correct 588 ms 760 KB Output is correct
22 Correct 551 ms 880 KB Output is correct
23 Correct 120 ms 888 KB Output is correct