#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] % MOD) % MOD;
(bp *= BASE) %= MOD;
}
return z;
}
array<int, N_> p, e;
int check() {
for (int i = 0; i < n * 2; ++i) p[i] = q[i];
map<ll, int> mp;
for (int ii = 0, jj = 0; ii < r; ++ii, ++jj) {
ll hh = hsh(p, 2 * n);
if (mp.count(hh)) {
int gap = jj - mp[hh];
int left = r - jj;
jj += left / gap * gap;
} else {
mp[hh] = jj;
}
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 'ull hsh(std::array<int, 2000>&, int)':
archery.cpp:19:24: error: 'MOD' was not declared in this scope
19 | z = (z + bp * a[i] % MOD) % MOD;
| ^~~
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;
| ~~~~~^~~~~~~~~~~~~
