oj.uz

답안 #433136

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433136 2021-06-18T22:46:22 Z rainboy Archery (IOI09_archery) C
14 / 100
 2000 ms 5548 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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