Submission #433134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433134	2021-06-18T22:39:30 Z	rainboy	Archery (IOI09_archery)	C	14 / 100	399 ms	6340 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_;
			} else
				x += sum[l];
			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:84:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d%d", &n, &r);
      |  ^~~~~~~~~~~~~~~~~~~~~
archery.c:86:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1

4.0 / 6.0

#	Verdict	Execution time	Memory	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	3 ms	332 KB	Output isn't correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct

Subtask #2

10.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	204 KB	Output isn't correct
2	Incorrect	1 ms	204 KB	Output isn't correct
3	Incorrect	2 ms	332 KB	Output isn't correct
4	Incorrect	14 ms	728 KB	Output isn't correct
5	Incorrect	215 ms	5712 KB	Output isn't correct
6	Incorrect	1 ms	204 KB	Output isn't correct
7	Incorrect	1 ms	204 KB	Output isn't correct
8	Correct	11 ms	724 KB	Output is correct
9	Incorrect	21 ms	956 KB	Output isn't correct
10	Correct	1 ms	332 KB	Output is correct
11	Incorrect	26 ms	980 KB	Output isn't correct
12	Incorrect	3 ms	332 KB	Output isn't correct
13	Incorrect	318 ms	3696 KB	Output isn't correct
14	Incorrect	8 ms	460 KB	Output isn't correct
15	Incorrect	66 ms	1152 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	7 ms	460 KB	Output isn't correct
21	Incorrect	20 ms	920 KB	Output isn't correct
22	Incorrect	49 ms	1120 KB	Output isn't correct
23	Incorrect	399 ms	5964 KB	Output isn't correct
24	Incorrect	0 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	18 ms	972 KB	Output isn't correct
28	Incorrect	113 ms	3780 KB	Output isn't correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	3 ms	460 KB	Output is correct
31	Incorrect	18 ms	892 KB	Output isn't correct
32	Incorrect	177 ms	5740 KB	Output isn't correct
33	Incorrect	0 ms	204 KB	Output isn't correct
34	Correct	0 ms	204 KB	Output is correct
35	Incorrect	2 ms	364 KB	Output isn't correct
36	Incorrect	2 ms	332 KB	Output isn't correct
37	Incorrect	16 ms	844 KB	Output isn't correct
38	Incorrect	21 ms	1036 KB	Output isn't correct
39	Incorrect	1 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	464 KB	Output isn't correct
44	Incorrect	8 ms	588 KB	Output isn't correct
45	Incorrect	19 ms	844 KB	Output isn't correct
46	Incorrect	19 ms	972 KB	Output isn't correct
47	Incorrect	188 ms	6340 KB	Output isn't correct