oj.uz

답안 #1067913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067913 2024-08-21T05:30:44 Z sleepntsheep Archery (IOI09_archery) C++17
20 / 100
 2000 ms 452 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <cstdio>
#include <map>
#include <array>
using namespace std;

using ll = long long;
using ull = unsigned long long;

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

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

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

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

	map<ull, int> mp;

	for (int ii = 0; ii < r; ++ii) {
		ull 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);
	if(n>N)return 1;
	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:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d", &n, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~
archery.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   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 0 ms 348 KB Execution failed because the return code was nonzero
3 Correct 49 ms 424 KB Output is correct
4 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
5 Correct 1 ms 348 KB Output is correct
6 Correct 143 ms 344 KB Output is correct

Subtask #2
16.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 191 ms 452 KB Output is correct
3 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
4 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
5 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
6 Correct 224 ms 440 KB Output is correct
7 Execution timed out 2079 ms 344 KB Time limit exceeded
8 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
9 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
10 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
11 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
12 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
13 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
14 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
15 Runtime error 1 ms 348 KB Execution failed because the return code was nonzero
16 Correct 268 ms 348 KB Output is correct
17 Runtime error 0 ms 344 KB Execution failed because the return code was nonzero
18 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
19 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
20 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
21 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
22 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
23 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
24 Correct 212 ms 348 KB Output is correct
25 Execution timed out 2040 ms 344 KB Time limit exceeded
26 Runtime error 1 ms 348 KB Execution failed because the return code was nonzero
27 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
28 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
29 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
30 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
31 Runtime error 0 ms 372 KB Execution failed because the return code was nonzero
32 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
33 Correct 277 ms 348 KB Output is correct
34 Correct 154 ms 344 KB Output is correct
35 Runtime error 1 ms 348 KB Execution failed because the return code was nonzero
36 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
37 Runtime error 1 ms 348 KB Execution failed because the return code was nonzero
38 Runtime error 1 ms 348 KB Execution failed because the return code was nonzero
39 Correct 261 ms 440 KB Output is correct
40 Execution timed out 2050 ms 344 KB Time limit exceeded
41 Runtime error 1 ms 348 KB Execution failed because the return code was nonzero
42 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
43 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
44 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
45 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
46 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
47 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero