Submission #433332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433332	2021-06-19T15:19:17 Z	rainboy	Archery (IOI09_archery)	C	70 / 100	2000 ms	15052 KB

archery

#include <assert.h>
#include <stdio.h>
#include <string.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 max(int a, int b) { return a > b ? a : b; }

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

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

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

void build(int n) {
	int i;

	n1 = n;
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		if (i < n)
			sum[n_ + i] = pref[n_ + i] = suf[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] = suf[i] = sum[i] += x;
	while (i > 1)
		pul(i >>= 1);
}

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

	x = y = 0;
	for (l = n_ + 0, r = n_ + i - 1; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0)
			x = max(x, suf[r] + y), y += sum[r], r--;
	x = max(x, suf[1] + y);
	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;
}

char used[N];

int solve_winners(int *kk, int n) {
	int i, j, k, sum;

	memset(used, 0, n * sizeof *used);
	k = 0, sum = 0;
	for (i = 0; i < n; i++)
		if (kk[i] > 0) {
			k = kk[i] - 1;
			if (i == 0 && k > 0)
				used[i] = 1, k--, sum ^= i;
			break;
		}
	for (j = i + 1; j <= i + n; j++) {
		if (j != i + n)
			k += kk[j % n];
		if (!used[j % n] && k > 0)
			used[j % n] = 1, k--, sum ^= j % n;
	}
	for (j = i + 1; j <= i + n; j++)
		if (!used[j % n] && k > 0)
			used[j % n] = 1, k--, sum ^= j % n;
	return sum;
}

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++) {
			int p1;

			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_;
			}
			p1 = solve_winners(kk, n), add(i), p1 ^= solve_winners(kk, n), delete(i);
			if (i < mn) {
				if (kk[mn] == 1 || mn == 0)
					delete(mn), p = add(mn);
				else
					delete(mn), delete(mn), add((mn + 1) % n), p = delete((mn + 1) % n), p ^= add(mn), p ^= add(mn);
			} else if (i > mn) {
				int push;

				delete(mn), push = kk[mn] == 2 && mn != 0;
				if (push)
					delete(mn), add((mn + 1) % n);
				p = add(i), delete(i);
				if (push)
					delete((mn + 1) % n), add(mn);
				add(mn);
			} else {
				if (mn == 0)
					delete(0), p = add(0);
				else
					delete(mn), p = add((i + 1) % n), delete((i + 1) % n), add(mn);
			}
			p = (p - r % n + n) % n;
			p1 = (p1 - r % n + n) % n;
			if (i > mn)
				assert(p == p1);
			if (p_ >= p1)
				p_ = p1, i_ = i;
		}
	}
	printf("%d\n", i_ + 1);
	return 0;
}

Compilation message

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

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	157 ms	400 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct

Subtask #2

64.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	204 KB	Output is correct
3	Correct	56 ms	344 KB	Output is correct
4	Execution timed out	2084 ms	844 KB	Time limit exceeded
5	Execution timed out	2063 ms	7492 KB	Time limit exceeded
6	Correct	2 ms	204 KB	Output is correct
7	Correct	22 ms	352 KB	Output is correct
8	Execution timed out	2081 ms	844 KB	Time limit exceeded
9	Execution timed out	2075 ms	1268 KB	Time limit exceeded
10	Correct	30 ms	332 KB	Output is correct
11	Execution timed out	2072 ms	1144 KB	Time limit exceeded
12	Correct	161 ms	396 KB	Output is correct
13	Execution timed out	2079 ms	4676 KB	Time limit exceeded
14	Correct	584 ms	512 KB	Output is correct
15	Execution timed out	2079 ms	1432 KB	Time limit exceeded
16	Runtime error	2 ms	460 KB	Execution killed with signal 6
17	Runtime error	3 ms	460 KB	Execution killed with signal 6
18	Runtime error	6 ms	588 KB	Execution killed with signal 6
19	Runtime error	11 ms	716 KB	Execution killed with signal 6
20	Runtime error	61 ms	836 KB	Execution killed with signal 6
21	Execution timed out	2075 ms	1280 KB	Time limit exceeded
22	Execution timed out	2094 ms	1336 KB	Time limit exceeded
23	Runtime error	504 ms	15052 KB	Execution killed with signal 6
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	5 ms	460 KB	Output is correct
27	Correct	26 ms	1188 KB	Output is correct
28	Correct	192 ms	4812 KB	Output is correct
29	Correct	2 ms	332 KB	Output is correct
30	Correct	4 ms	460 KB	Output is correct
31	Correct	25 ms	1136 KB	Output is correct
32	Correct	245 ms	7472 KB	Output is correct
33	Correct	1 ms	204 KB	Output is correct
34	Correct	1 ms	204 KB	Output is correct
35	Correct	3 ms	332 KB	Output is correct
36	Correct	3 ms	332 KB	Output is correct
37	Correct	21 ms	1068 KB	Output is correct
38	Correct	31 ms	1228 KB	Output is correct
39	Correct	1 ms	204 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct
41	Correct	3 ms	332 KB	Output is correct
42	Correct	3 ms	332 KB	Output is correct
43	Correct	6 ms	460 KB	Output is correct
44	Correct	11 ms	700 KB	Output is correct
45	Correct	23 ms	1148 KB	Output is correct
46	Correct	28 ms	1212 KB	Output is correct
47	Correct	281 ms	8000 KB	Output is correct