oj.uz

Submission #433335

# Submission time Handle Problem Language Result Execution time Memory
433335 2021-06-19T15:23:17 Z rainboy Archery (IOI09_archery) C
80 / 100
 2000 ms 8040 KB 
#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] > 0 && 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 1 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 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #2
74.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 52 ms 332 KB Output is correct
4 Execution timed out 2074 ms 832 KB Time limit exceeded
5 Execution timed out 2069 ms 7520 KB Time limit exceeded
6 Correct 2 ms 204 KB Output is correct
7 Correct 21 ms 332 KB Output is correct
8 Execution timed out 2077 ms 844 KB Time limit exceeded
9 Execution timed out 2077 ms 1176 KB Time limit exceeded
10 Correct 30 ms 364 KB Output is correct
11 Execution timed out 2082 ms 1100 KB Time limit exceeded
12 Correct 161 ms 408 KB Output is correct
13 Execution timed out 2079 ms 4676 KB Time limit exceeded
14 Correct 574 ms 508 KB Output is correct
15 Execution timed out 2086 ms 1460 KB Time limit exceeded
16 Correct 2 ms 204 KB Output is correct
17 Correct 40 ms 332 KB Output is correct
18 Correct 91 ms 372 KB Output is correct
19 Correct 272 ms 428 KB Output is correct
20 Correct 551 ms 580 KB Output is correct
21 Execution timed out 2074 ms 1288 KB Time limit exceeded
22 Execution timed out 2078 ms 1356 KB Time limit exceeded
23 Execution timed out 2066 ms 7544 KB Time limit exceeded
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 27 ms 1184 KB Output is correct
28 Correct 158 ms 4748 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 1100 KB Output is correct
32 Correct 235 ms 7476 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 2 ms 332 KB Output is correct
36 Correct 3 ms 332 KB Output is correct
37 Correct 21 ms 1100 KB Output is correct
38 Correct 29 ms 1204 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 1 ms 332 KB Output is correct
41 Correct 2 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 744 KB Output is correct
45 Correct 23 ms 1156 KB Output is correct
46 Correct 27 ms 1208 KB Output is correct
47 Correct 260 ms 8040 KB Output is correct