Submission #433922

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433922	2021-06-20T12:15:15 Z	rainboy	Garage (IOI09_garage)	C	100 / 100	1 ms	332 KB

garage

#include <stdio.h>

#define N	100
#define M	2000

int iq[1 + N], pq[N], cnt;

int lt(int i, int j) { return i < j; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	static int rr[N], ww[M], ii[M], qu[M];
	int n, m, h, i, j, head, cnt_, ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &rr[i]);
		pq_add(i);
	}
	for (j = 0; j < m; j++)
		scanf("%d", &ww[j]);
	head = cnt_ = 0;
	for (h = 0; h < m * 2; h++) {
		scanf("%d", &j);
		if (j > 0) {
			j--;
			if (cnt)
				ii[j] = pq_remove_first();
			else
				qu[head + cnt_++] = j;
		} else {
			j = -j - 1;
			if (cnt_)
				ii[qu[cnt_--, head++]] = ii[j];
			else
				pq_add(ii[j]);
		}
	}
	ans = 0;
	for (j = 0; j < m; j++)
		ans += ww[j] * rr[ii[j]];
	printf("%d\n", ans);
	return 0;
}

Compilation message

garage.c: In function 'main':
garage.c:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
garage.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d", &rr[i]);
      |   ^~~~~~~~~~~~~~~~~~~
garage.c:53:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d", &ww[j]);
      |   ^~~~~~~~~~~~~~~~~~~
garage.c:56:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d", &j);
      |   ^~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	276 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	280 KB	Output is correct
9	Correct	1 ms	280 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	284 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	280 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	288 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct