oj.uz

답안 #1067905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067905 2024-08-21T05:27:05 Z sleepntsheep Archery (IOI09_archery) C++17
20 / 100
 2000 ms 604 KB 
#include <cstdio>
#include <map>
#include <array>
using namespace std;

using ll = long long;

#define N 400
#define N_ (2*N)

int n, r, s[N_], ans = 1e9, q[N_], opt;

ll hsh(array<int, N_> &a, int n) {
	const ll BASE = 10001, MOD = 1000000007;
	ll z = 0, bp = 1;
	for (int i = 0; i < n; ++i) {
		z = (z + bp * a[i] % MOD) % MOD;
		(bp *= BASE) %= MOD;
	}
	return z;
}

int check() {
	array<int, N_> p, e;
	for (int i = 0; i < n * 2; ++i) p[i] = q[i];

	map<ll, int> mp;

	for (int ii = 0; ii < r; ++ii) {
		ll hh = hsh(p, 2 * n);
		if (mp.count(hh)) {
			int gap = ii - mp[hh];
			int left = r - ii;
			r = ii + left % gap;
		} else {
			mp[hh] = ii;
		}

		int u = p[0], v = p[1];
		if (s[u] < s[v]) e[0] = u, e[n * 2 - 1] = v;
		else e[0] = v, e[n * 2 - 1] = u;

		for (int j = 2; j < n * 2; j += 2) {
			int u = p[j], v = p[j + 1];
			if (s[u] < s[v]) {
				e[(j - 2) + 1] = u;
				e[j] = v;
			} else {
				e[1 + (j - 2)] = v;
				e[j] = u;
			}
		}
		p = e;


	}

	for (int i = 0; i < N_; ++i) if (e[i] == 0) return (i + 1) / 2;
	__builtin_unreachable();
}

int main() {
	scanf("%d%d", &n, &r);
	for (int i = 0; i < n * 2; ++i)
		scanf("%d", s + i), q[i] = i;

	if (ans >= check()) ans = check(), opt = 1;

	for (int i = 1; i < n * 2; ++i) {
		int o = 0;
		for (int j = 1; j <= i; ++j) q[o++] = j;
		q[o++] = 0;
		for (int j = i + 1; j < n * 2; ++j) q[o++] = j;

		if (ans >= check()) ans = check(), opt = (i + 2) / 2;
	}

	printf("%d", opt);
}

Compilation message

archery.cpp: In function 'int main()':
archery.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%d%d", &n, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~
archery.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d", s + i), q[i] = i;
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 3 ms 604 KB Execution killed with signal 6
3 Correct 138 ms 416 KB Output is correct
4 Runtime error 1 ms 344 KB Execution killed with signal 11
5 Correct 1 ms 428 KB Output is correct
6 Correct 436 ms 428 KB Output is correct

Subtask #2
16.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 436 KB Output is correct
2 Correct 641 ms 432 KB Output is correct
3 Runtime error 10 ms 604 KB Execution killed with signal 11
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Runtime error 1 ms 600 KB Execution killed with signal 11
6 Correct 658 ms 348 KB Output is correct
7 Runtime error 4 ms 600 KB Execution killed with signal 6
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Runtime error 1 ms 348 KB Execution killed with signal 11
10 Execution timed out 2078 ms 460 KB Time limit exceeded
11 Runtime error 1 ms 348 KB Execution killed with signal 11
12 Runtime error 1 ms 348 KB Execution killed with signal 11
13 Runtime error 1 ms 348 KB Execution killed with signal 11
14 Runtime error 7 ms 604 KB Execution killed with signal 6
15 Runtime error 1 ms 348 KB Execution killed with signal 11
16 Correct 827 ms 428 KB Output is correct
17 Runtime error 1 ms 348 KB Execution killed with signal 11
18 Runtime error 0 ms 348 KB Execution killed with signal 11
19 Incorrect 730 ms 424 KB Output isn't correct
20 Runtime error 1 ms 348 KB Execution killed with signal 11
21 Runtime error 1 ms 344 KB Execution killed with signal 11
22 Runtime error 1 ms 348 KB Execution killed with signal 11
23 Runtime error 1 ms 348 KB Execution killed with signal 11
24 Correct 640 ms 428 KB Output is correct
25 Runtime error 1 ms 348 KB Execution killed with signal 11
26 Runtime error 1 ms 348 KB Execution killed with signal 11
27 Runtime error 1 ms 348 KB Execution killed with signal 11
28 Runtime error 1 ms 348 KB Execution killed with signal 11
29 Runtime error 1 ms 348 KB Execution killed with signal 11
30 Runtime error 0 ms 348 KB Execution killed with signal 11
31 Runtime error 0 ms 348 KB Execution killed with signal 11
32 Runtime error 0 ms 348 KB Execution killed with signal 11
33 Correct 740 ms 432 KB Output is correct
34 Correct 470 ms 348 KB Output is correct
35 Runtime error 1 ms 348 KB Execution killed with signal 11
36 Runtime error 1 ms 348 KB Execution killed with signal 11
37 Runtime error 0 ms 348 KB Execution killed with signal 11
38 Runtime error 1 ms 348 KB Execution killed with signal 11
39 Correct 776 ms 348 KB Output is correct
40 Runtime error 0 ms 348 KB Execution killed with signal 11
41 Runtime error 1 ms 348 KB Execution killed with signal 11
42 Runtime error 1 ms 488 KB Execution killed with signal 11
43 Execution timed out 2094 ms 448 KB Time limit exceeded
44 Runtime error 1 ms 348 KB Execution killed with signal 11
45 Runtime error 1 ms 348 KB Execution killed with signal 11
46 Runtime error 1 ms 348 KB Execution killed with signal 11
47 Runtime error 1 ms 348 KB Execution killed with signal 11