Submission #433136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433136	2021-06-18T22:46:22 Z	rainboy	Archery (IOI09_archery)	C	14 / 100	2000 ms	5548 KB

archery

#include <assert.h>
#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], n1, 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;

	n1 = n;
	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) {
	int h;

	update(i, 1), kk[i]++;
	for (h = 0; h < n_; h++)
		assert(kk[h] - (h < n1) == sum[n_ + h]);
	return query(i);
}

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

	update(i, -1), kk[i]--;
	for (h = 0; h < n_; h++)
		assert(kk[h] - (h < n1) == sum[n_ + h]);
	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:92:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d%d", &n, &r);
      |  ^~~~~~~~~~~~~~~~~~~~~
archery.c:94:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   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	236 KB	Output isn't correct
4	Incorrect	55 ms	372 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	1 ms	204 KB	Output isn't correct
2	Incorrect	1 ms	204 KB	Output isn't correct
3	Incorrect	21 ms	332 KB	Output isn't correct
4	Incorrect	1449 ms	708 KB	Output isn't correct
5	Execution timed out	2074 ms	5208 KB	Time limit exceeded
6	Incorrect	1 ms	204 KB	Output isn't correct
7	Incorrect	8 ms	204 KB	Output isn't correct
8	Correct	982 ms	704 KB	Output is correct
9	Execution timed out	2079 ms	892 KB	Time limit exceeded
10	Correct	11 ms	336 KB	Output is correct
11	Execution timed out	2080 ms	1080 KB	Time limit exceeded
12	Incorrect	81 ms	332 KB	Output isn't correct
13	Execution timed out	2079 ms	3636 KB	Time limit exceeded
14	Incorrect	402 ms	444 KB	Output isn't correct
15	Execution timed out	2082 ms	1132 KB	Time limit exceeded
16	Incorrect	1 ms	204 KB	Output isn't correct
17	Incorrect	33 ms	344 KB	Output isn't correct
18	Incorrect	42 ms	332 KB	Output isn't correct
19	Incorrect	145 ms	392 KB	Output isn't correct
20	Incorrect	371 ms	576 KB	Output isn't correct
21	Execution timed out	2085 ms	844 KB	Time limit exceeded
22	Execution timed out	2091 ms	1200 KB	Time limit exceeded
23	Execution timed out	2090 ms	5192 KB	Time limit exceeded
24	Incorrect	1 ms	204 KB	Output isn't correct
25	Incorrect	5 ms	332 KB	Output isn't correct
26	Incorrect	167 ms	460 KB	Output isn't correct
27	Execution timed out	2070 ms	1004 KB	Time limit exceeded
28	Execution timed out	2079 ms	3396 KB	Time limit exceeded
29	Correct	16 ms	344 KB	Output is correct
30	Correct	134 ms	428 KB	Output is correct
31	Execution timed out	2079 ms	860 KB	Time limit exceeded
32	Execution timed out	2085 ms	5080 KB	Time limit exceeded
33	Incorrect	1 ms	204 KB	Output isn't correct
34	Correct	1 ms	204 KB	Output is correct
35	Incorrect	28 ms	332 KB	Output isn't correct
36	Incorrect	36 ms	332 KB	Output isn't correct
37	Execution timed out	2074 ms	956 KB	Time limit exceeded
38	Execution timed out	2074 ms	1136 KB	Time limit exceeded
39	Incorrect	1 ms	204 KB	Output isn't correct
40	Incorrect	5 ms	332 KB	Output isn't correct
41	Incorrect	34 ms	356 KB	Output isn't correct
42	Incorrect	44 ms	332 KB	Output isn't correct
43	Incorrect	184 ms	452 KB	Output isn't correct
44	Incorrect	603 ms	596 KB	Output isn't correct
45	Execution timed out	2081 ms	1024 KB	Time limit exceeded
46	Execution timed out	2058 ms	896 KB	Time limit exceeded
47	Execution timed out	2083 ms	5548 KB	Time limit exceeded