oj.uz

답안 #1067900

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

using ll = long long;

#define N 5000
#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 344 KB Output is correct
2 Execution timed out 2085 ms 572 KB Time limit exceeded
3 Correct 218 ms 600 KB Output is correct
4 Execution timed out 2053 ms 588 KB Time limit exceeded
5 Correct 2 ms 344 KB Output is correct
6 Correct 571 ms 348 KB Output is correct

Subtask #2
16.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 344 KB Output is correct
2 Correct 771 ms 508 KB Output is correct
3 Execution timed out 2065 ms 676 KB Time limit exceeded
4 Runtime error 2 ms 604 KB Execution killed with signal 11
5 Runtime error 1 ms 860 KB Execution killed with signal 11
6 Correct 894 ms 504 KB Output is correct
7 Execution timed out 2020 ms 600 KB Time limit exceeded
8 Runtime error 2 ms 604 KB Execution killed with signal 11
9 Runtime error 1 ms 684 KB Execution killed with signal 11
10 Execution timed out 2091 ms 580 KB Time limit exceeded
11 Runtime error 2 ms 604 KB Execution killed with signal 11
12 Execution timed out 2048 ms 852 KB Time limit exceeded
13 Runtime error 2 ms 604 KB Execution killed with signal 11
14 Execution timed out 2094 ms 1100 KB Time limit exceeded
15 Execution timed out 2054 ms 1104 KB Time limit exceeded
16 Correct 1061 ms 512 KB Output is correct
17 Execution timed out 2025 ms 600 KB Time limit exceeded
18 Execution timed out 2080 ms 596 KB Time limit exceeded
19 Execution timed out 2013 ms 1100 KB Time limit exceeded
20 Execution timed out 2095 ms 1356 KB Time limit exceeded
21 Runtime error 2 ms 856 KB Execution killed with signal 11
22 Runtime error 1 ms 860 KB Execution killed with signal 11
23 Runtime error 1 ms 700 KB Execution killed with signal 11
24 Correct 845 ms 348 KB Output is correct
25 Execution timed out 2061 ms 604 KB Time limit exceeded
26 Execution timed out 2085 ms 1124 KB Time limit exceeded
27 Runtime error 1 ms 856 KB Execution killed with signal 11
28 Runtime error 2 ms 604 KB Execution killed with signal 11
29 Execution timed out 2096 ms 608 KB Time limit exceeded
30 Execution timed out 2027 ms 1108 KB Time limit exceeded
31 Runtime error 2 ms 604 KB Execution killed with signal 11
32 Runtime error 1 ms 688 KB Execution killed with signal 11
33 Correct 944 ms 508 KB Output is correct
34 Correct 612 ms 344 KB Output is correct
35 Execution timed out 2052 ms 604 KB Time limit exceeded
36 Execution timed out 2065 ms 648 KB Time limit exceeded
37 Execution timed out 2059 ms 1008 KB Time limit exceeded
38 Runtime error 2 ms 856 KB Execution killed with signal 11
39 Correct 1049 ms 508 KB Output is correct
40 Execution timed out 2081 ms 604 KB Time limit exceeded
41 Execution timed out 2053 ms 600 KB Time limit exceeded
42 Execution timed out 2069 ms 812 KB Time limit exceeded
43 Execution timed out 2040 ms 1108 KB Time limit exceeded
44 Execution timed out 2041 ms 848 KB Time limit exceeded
45 Runtime error 2 ms 600 KB Execution killed with signal 11
46 Runtime error 2 ms 604 KB Execution killed with signal 11
47 Runtime error 2 ms 604 KB Execution killed with signal 11