답안 #433118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433118	2021-06-18T21:31:27 Z	rainboy	Archery (IOI09_archery)	C	7 / 100	376 ms	6228 KB

archery

#include <stdio.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */

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

int pref[N_ * 2], sum[N_ * 2], n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	pref[i] = min(pref[l], sum[l] + pref[r]);
	sum[i] = sum[l] + sum[r];
}

void build(int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		if (i < n)
			sum[n_ + i] = pref[n_ + i] = -1;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

int kk[N];

void update(int i, int x) {
	i += n_;
	pref[i] = sum[i] += x;
	while (i > 1)
		pul(i >>= 1);
}

int query(int i) {
	int l, r, x;

	x = 0;
	for (l = n_ + i, r = n_ + n_ - 1; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (x + pref[l] <= 0) {
				i = l;
				while (i < n_)
					if (x + pref[i << 1 | 0] <= 0)
						i = i << 1 | 0;
					else
						x += sum[i << 1 | 0], i = i << 1 | 1;
				return i - n_;
			}
			l++;
		}
	if (x + pref[1] <= 0)
		return -1;
	i = 1;
	while (i < n_)
		if (x + pref[i << 1 | 0] <= 0)
			i = i << 1 | 0;
		else
			x += sum[i << 1 | 0], i = i << 1 | 1;
	return i - n_;
}

int add(int i) {
	update(i, 1), kk[i]++;
	return query(i);
}

int delete(int i) {
	int j = query(i);

	update(i, -1), kk[i]--;
	return j;
}

int main() {
	static int aa[N * 2];
	int n, r, p, p_, i, i_, a_, mn;

	scanf("%d%d", &n, &r);
	for (i = 0; i < n * 2; i++)
		scanf("%d", &aa[i]), aa[i]--;
	build(n);
	a_ = aa[0];
	if (a_ == 0)
		i_ = n - 1;
	else if (a_ > n) {
		add(n - 1 - 0);
		for (i = 0; i < n * 2; i++)
			if (aa[i] > a_)
				add(n - 1 - (i / 2));
		p_ = n, i_ = -1;
		for (i = 0; i < n; i++) {
			if (i > 0) {
				if (aa[i * 2] > a_)
					delete(n - 1 - i), add(n - 1 - (i - 1));
				aa[(i - 1) * 2] = aa[i * 2], aa[i * 2] = a_;
			}
			p = n - 1 - add(n - 1 - i), delete(n - 1 - i);
			if (p_ >= p)
				p_ = p, i_ = i;
		}
	} else {
		for (i = 0; i < n * 2; i++)
			if (aa[i] < a_)
				add(i / 2);
		mn = 0;
		while (kk[mn] == 0)
			mn++;
		p_ = n, i_ = -1;
		for (i = 0; i < n; i++) {
			if (i > 0) {
				if (aa[i * 2] < a_) {
					delete(i), add(i - 1);
					if (mn == i)
						mn--;
				}
				aa[(i - 1) * 2] = aa[i * 2], aa[i * 2] = a_;
			}
			if (i < mn) {
				p = delete(mn);
				if (kk[mn] > 0)
					p ^= delete(mn), p ^= add((mn + 1) % n), delete((mn + 1) % n), add(mn);
				add(mn);
			} else if (i > mn) {
				p = delete(mn);
				if (kk[mn] > 0)
					p ^= delete(mn), p ^= add((mn + 1) % n), delete((mn + 1) % n), add(mn);
				p ^= add(i), delete(i);
				add(mn);
			} else
				p = add((i + 1) % n), delete((i + 1) % n);
			p = (p - r % n + n) % n;
			if (p_ >= p)
				p_ = p, i_ = i;
		}
	}
	printf("%d\n", i_ + 1);
	return 0;
}

Compilation message

archery.c: In function 'main':
archery.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d", &n, &r);
      |  ^~~~~~~~~~~~~~~~~~~~~
archery.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1

3.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Incorrect	1 ms	204 KB	Output isn't correct
4	Incorrect	2 ms	332 KB	Output isn't correct
5	Correct	0 ms	204 KB	Output is correct
6	Incorrect	1 ms	204 KB	Output isn't correct

Subtask #2

4.0 / 94.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Incorrect	0 ms	204 KB	Output isn't correct
3	Incorrect	1 ms	332 KB	Output isn't correct
4	Incorrect	14 ms	800 KB	Output isn't correct
5	Incorrect	210 ms	5652 KB	Output isn't correct
6	Incorrect	1 ms	204 KB	Output isn't correct
7	Incorrect	1 ms	332 KB	Output isn't correct
8	Correct	11 ms	776 KB	Output is correct
9	Incorrect	22 ms	972 KB	Output isn't correct
10	Correct	1 ms	332 KB	Output is correct
11	Incorrect	26 ms	1028 KB	Output isn't correct
12	Incorrect	3 ms	332 KB	Output isn't correct
13	Incorrect	308 ms	3776 KB	Output isn't correct
14	Incorrect	9 ms	460 KB	Output isn't correct
15	Incorrect	63 ms	1224 KB	Output isn't correct
16	Incorrect	1 ms	204 KB	Output isn't correct
17	Incorrect	2 ms	332 KB	Output isn't correct
18	Incorrect	3 ms	332 KB	Output isn't correct
19	Incorrect	5 ms	332 KB	Output isn't correct
20	Incorrect	6 ms	460 KB	Output isn't correct
21	Incorrect	19 ms	992 KB	Output isn't correct
22	Incorrect	48 ms	1196 KB	Output isn't correct
23	Incorrect	376 ms	5896 KB	Output isn't correct
24	Incorrect	1 ms	204 KB	Output isn't correct
25	Incorrect	1 ms	332 KB	Output isn't correct
26	Incorrect	4 ms	460 KB	Output isn't correct
27	Incorrect	17 ms	1036 KB	Output isn't correct
28	Incorrect	97 ms	3796 KB	Output isn't correct
29	Incorrect	1 ms	332 KB	Output isn't correct
30	Incorrect	4 ms	460 KB	Output isn't correct
31	Incorrect	16 ms	912 KB	Output isn't correct
32	Incorrect	148 ms	5712 KB	Output isn't correct
33	Incorrect	1 ms	204 KB	Output isn't correct
34	Incorrect	0 ms	204 KB	Output isn't correct
35	Incorrect	2 ms	332 KB	Output isn't correct
36	Incorrect	2 ms	332 KB	Output isn't correct
37	Incorrect	13 ms	952 KB	Output isn't correct
38	Incorrect	20 ms	1112 KB	Output isn't correct
39	Incorrect	0 ms	204 KB	Output isn't correct
40	Incorrect	1 ms	332 KB	Output isn't correct
41	Incorrect	2 ms	332 KB	Output isn't correct
42	Incorrect	2 ms	332 KB	Output isn't correct
43	Incorrect	4 ms	460 KB	Output isn't correct
44	Incorrect	7 ms	660 KB	Output isn't correct
45	Incorrect	15 ms	1004 KB	Output isn't correct
46	Incorrect	17 ms	1056 KB	Output isn't correct
47	Incorrect	169 ms	6228 KB	Output isn't correct