Submission #1067908

#TimeUsernameProblemLanguageResultExecution timeMemory
1067908sleepntsheepArchery (IOI09_archery)C++17
Compilation error
0 ms0 KiB
#pragma GCC optimize("O3,unroll-loops") #include <cstdio> #include <map> #include <array> using namespace std; using ll = long long; #define N 400 #define N_ (2*N) int n, r, s[N_], ans = 1e9, q[N_], opt; ll hsh(array<int, N_> &a, int n) { constexpr 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; } 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; 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); 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); } #include <cstdio> #include <map> #include <array> using namespace std; using ll = long long; #define N 400 #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; } 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; 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); 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 (stderr)

archery.cpp:94:5: error: redefinition of 'int n'
   94 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |     ^
archery.cpp:12:5: note: 'int n' previously declared here
   12 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |     ^
archery.cpp:94:8: error: redefinition of 'int r'
   94 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |        ^
archery.cpp:12:8: note: 'int r' previously declared here
   12 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |        ^
archery.cpp:94:11: error: redefinition of 'int s [800]'
   94 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |           ^
archery.cpp:12:11: note: 'int s [800]' previously declared here
   12 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |           ^
archery.cpp:94:18: error: redefinition of 'int ans'
   94 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |                  ^~~
archery.cpp:12:18: note: 'int ans' previously defined here
   12 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |                  ^~~
archery.cpp:94:29: error: redefinition of 'int q [800]'
   94 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |                             ^
archery.cpp:12:29: note: 'int q [800]' previously declared here
   12 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |                             ^
archery.cpp:94:36: error: redefinition of 'int opt'
   94 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |                                    ^~~
archery.cpp:12:36: note: 'int opt' previously declared here
   12 | int n, r, s[N_], ans = 1e9, q[N_], opt;
      |                                    ^~~
archery.cpp:96:4: error: redefinition of 'll hsh(std::array<int, 800>&, int)'
   96 | ll hsh(array<int, N_> &a, int n) {
      |    ^~~
archery.cpp:14:4: note: 'll hsh(std::array<int, 800>&, int)' previously defined here
   14 | ll hsh(array<int, N_> &a, int n) {
      |    ^~~
archery.cpp:106:16: error: redefinition of 'std::array<int, 800> p'
  106 | array<int, N_> p, e;
      |                ^
archery.cpp:24:16: note: 'std::array<int, 800> p' previously declared here
   24 | array<int, N_> p, e;
      |                ^
archery.cpp:106:19: error: redefinition of 'std::array<int, 800> e'
  106 | array<int, N_> p, e;
      |                   ^
archery.cpp:24:19: note: 'std::array<int, 800> e' previously declared here
   24 | array<int, N_> p, e;
      |                   ^
archery.cpp:107:5: error: redefinition of 'int check()'
  107 | int check() {
      |     ^~~~~
archery.cpp:25:5: note: 'int check()' previously defined here
   25 | int check() {
      |     ^~~~~
archery.cpp:145:5: error: redefinition of 'int main()'
  145 | int main() {
      |     ^~~~
archery.cpp:63:5: note: 'int main()' previously defined here
   63 | int main() {
      |     ^~~~
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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d", s + i), q[i] = i;
      |   ~~~~~^~~~~~~~~~~~~
archery.cpp: In function 'int main()':
archery.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |  scanf("%d%d", &n, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~
archery.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |   scanf("%d", s + i), q[i] = i;
      |   ~~~~~^~~~~~~~~~~~~