oj.uz

답안 #1067896

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

using ll = long long;

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

ll hsh(array<int, 400> &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, 400> 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 < 400; ++i) if (e[i] == 0) return (i + 1) / 2;
	__builtin_unreachable();
}

int main() {
	scanf("%d%d", &n, &r);
	if (n > 200) { while(1)puts("EEEEEEEE"); }
	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:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d%d", &n, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~
archery.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   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 Execution timed out 2406 ms 65536 KB Time limit exceeded
3 Correct 134 ms 348 KB Output is correct
4 Execution timed out 2323 ms 65536 KB Time limit exceeded
5 Correct 1 ms 348 KB Output is correct
6 Correct 434 ms 424 KB Output is correct

Subtask #2
16.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 344 KB Output is correct
2 Correct 604 ms 348 KB Output is correct
3 Execution timed out 2397 ms 65536 KB Time limit exceeded
4 Execution timed out 2376 ms 65536 KB Time limit exceeded
5 Execution timed out 2427 ms 65536 KB Time limit exceeded
6 Correct 668 ms 420 KB Output is correct
7 Execution timed out 2267 ms 65536 KB Time limit exceeded
8 Execution timed out 2434 ms 65536 KB Time limit exceeded
9 Execution timed out 2419 ms 65536 KB Time limit exceeded
10 Execution timed out 2281 ms 65536 KB Time limit exceeded
11 Execution timed out 2404 ms 65536 KB Time limit exceeded
12 Execution timed out 2041 ms 65536 KB Time limit exceeded
13 Execution timed out 2393 ms 65536 KB Time limit exceeded
14 Execution timed out 2444 ms 65536 KB Time limit exceeded
15 Execution timed out 2249 ms 65536 KB Time limit exceeded
16 Correct 826 ms 348 KB Output is correct
17 Execution timed out 2388 ms 65544 KB Time limit exceeded
18 Execution timed out 2374 ms 65536 KB Time limit exceeded
19 Execution timed out 2444 ms 65536 KB Time limit exceeded
20 Execution timed out 2392 ms 65536 KB Time limit exceeded
21 Runtime error 1758 ms 65536 KB Execution killed with signal 9
22 Execution timed out 2376 ms 65536 KB Time limit exceeded
23 Execution timed out 2397 ms 65536 KB Time limit exceeded
24 Correct 632 ms 348 KB Output is correct
25 Execution timed out 2277 ms 65536 KB Time limit exceeded
26 Execution timed out 2401 ms 65536 KB Time limit exceeded
27 Execution timed out 2432 ms 65536 KB Time limit exceeded
28 Runtime error 1784 ms 65536 KB Execution killed with signal 9
29 Execution timed out 2373 ms 65536 KB Time limit exceeded
30 Execution timed out 2355 ms 65536 KB Time limit exceeded
31 Execution timed out 2430 ms 65540 KB Time limit exceeded
32 Runtime error 221 ms 65536 KB Execution killed with signal 9
33 Correct 742 ms 344 KB Output is correct
34 Correct 471 ms 420 KB Output is correct
35 Execution timed out 2382 ms 65536 KB Time limit exceeded
36 Execution timed out 2410 ms 65536 KB Time limit exceeded
37 Execution timed out 2323 ms 65536 KB Time limit exceeded
38 Execution timed out 2383 ms 65536 KB Time limit exceeded
39 Correct 773 ms 436 KB Output is correct
40 Execution timed out 2330 ms 65536 KB Time limit exceeded
41 Execution timed out 2375 ms 65536 KB Time limit exceeded
42 Execution timed out 2308 ms 65536 KB Time limit exceeded
43 Execution timed out 2380 ms 65536 KB Time limit exceeded
44 Execution timed out 2327 ms 65536 KB Time limit exceeded
45 Execution timed out 2457 ms 65536 KB Time limit exceeded
46 Execution timed out 2380 ms 65536 KB Time limit exceeded
47 Execution timed out 2426 ms 65540 KB Time limit exceeded