#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;
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
