Submission #1067873

#TimeUsernameProblemLanguageResultExecution timeMemory
1067873sleepntsheepArchery (IOI09_archery)C++17
Compilation error
0 ms0 KiB
#include <cstdio> #include <map> #include <array> using namespace std; using ll = long long; int n, r, s[400], ans = 1e9, q[400], opt; ll hash(array<int, 400> &a, int n) { const BASE = 137, 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 = hash(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); 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 (stderr)

archery.cpp: In function 'll hash(std::array<int, 400>&, int)':
archery.cpp:11:8: error: 'BASE' does not name a type
   11 |  const BASE = 137, MOD = 1000000007;
      |        ^~~~
archery.cpp:14:24: error: 'MOD' was not declared in this scope
   14 |   z = (z + bp * a[i] % MOD) % MOD;
      |                        ^~~
archery.cpp:15:10: error: 'BASE' was not declared in this scope
   15 |   (bp *= BASE) %= MOD;
      |          ^~~~
archery.cpp: In function 'int check()':
archery.cpp:27:11: error: reference to 'hash' is ambiguous
   27 |   ll hh = hash(p, 2 * n);
      |           ^~~~
In file included from /usr/include/c++/10/optional:42,
                 from /usr/include/c++/10/bits/node_handle.h:39,
                 from /usr/include/c++/10/bits/stl_tree.h:72,
                 from /usr/include/c++/10/map:60,
                 from archery.cpp:2:
/usr/include/c++/10/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
archery.cpp:10:4: note:                 'll hash(std::array<int, 400>&, int)'
   10 | ll hash(array<int, 400> &a, int n) {
      |    ^~~~
archery.cpp: In function 'int main()':
archery.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d", &n, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~
archery.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d", s + i), q[i] = i;
      |   ~~~~~^~~~~~~~~~~~~