oj.uz

답안 #433131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433131 2021-06-18T22:24:25 Z rainboy Archery (IOI09_archery) C
14 / 100
 2000 ms 6312 KB 
#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) {
#if 0
	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_;
			}
			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_;
#else
	int j, x;

	x = 0;
	for (j = i; j < n_; j++) {
		x += sum[n_ + j];
		if (x <= 0)
			return j;
	}
	for (j = 0; j < i; j++) {
		x += sum[n_ + j];
		if (x <= 0)
			return j;
	}
	return -1;
#endif
}

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:100:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d%d", &n, &r);
      |  ^~~~~~~~~~~~~~~~~~~~~
archery.c:102:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   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 256 KB Output isn't correct
4 Incorrect 2 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Incorrect 17 ms 716 KB Output isn't correct
5 Execution timed out 2070 ms 5568 KB Time limit exceeded
6 Incorrect 1 ms 204 KB Output isn't correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Correct 11 ms 720 KB Output is correct
9 Incorrect 143 ms 948 KB Output isn't correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 22 ms 908 KB Output isn't correct
12 Incorrect 3 ms 332 KB Output isn't correct
13 Incorrect 1408 ms 3756 KB Output isn't correct
14 Incorrect 7 ms 460 KB Output isn't correct
15 Incorrect 76 ms 1160 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 9 ms 352 KB Output isn't correct
19 Incorrect 8 ms 396 KB Output isn't correct
20 Incorrect 16 ms 456 KB Output isn't correct
21 Incorrect 31 ms 924 KB Output isn't correct
22 Incorrect 104 ms 1132 KB Output isn't correct
23 Incorrect 1403 ms 5816 KB Output isn't correct
24 Incorrect 1 ms 204 KB Output isn't correct
25 Incorrect 2 ms 332 KB Output isn't correct
26 Incorrect 9 ms 420 KB Output isn't correct
27 Incorrect 197 ms 952 KB Output isn't correct
28 Execution timed out 2064 ms 3768 KB Time limit exceeded
29 Correct 3 ms 332 KB Output is correct
30 Correct 16 ms 460 KB Output is correct
31 Incorrect 167 ms 880 KB Output isn't correct
32 Execution timed out 2069 ms 5384 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 2 ms 332 KB Output isn't correct
36 Incorrect 3 ms 332 KB Output isn't correct
37 Incorrect 18 ms 852 KB Output isn't correct
38 Incorrect 51 ms 1028 KB Output isn't correct
39 Incorrect 1 ms 204 KB Output isn't correct
40 Incorrect 2 ms 328 KB Output isn't correct
41 Incorrect 4 ms 332 KB Output isn't correct
42 Incorrect 4 ms 332 KB Output isn't correct
43 Incorrect 12 ms 460 KB Output isn't correct
44 Incorrect 26 ms 604 KB Output isn't correct
45 Incorrect 123 ms 916 KB Output isn't correct
46 Incorrect 61 ms 972 KB Output isn't correct
47 Incorrect 1248 ms 6312 KB Output isn't correct