Submission #1102921

#TimeUsernameProblemLanguageResultExecution timeMemory
1102921MateiKing80The Collection Game (BOI21_swaps)C++14
100 / 100
6 ms804 KiB
#include <bits/stdc++.h> #include "swaps.h" using namespace std; const int MAXN = 50; vector<array<int, 2>> ops[MAXN]; int sz, n; int bitonic(int l, int r, bool inc, int lvl, bool isbitonic) { if(l == r) return lvl - 1; int md = (l + r) >> 1, mx = lvl - 1; if(!isbitonic) { mx = bitonic(l, md, inc, lvl, 0); bitonic(md + 1, r, !inc, lvl, 0); } for(int i = l; i <= md; i++) { int x = i, y = i + md + 1 - l; if(!inc) ops[mx + 1].push_back({x, y}); else ops[mx + 1].push_back({y, x}); } bitonic(l, md, inc, mx + 2, 1); return bitonic(md + 1, r, inc, mx + 2, 1); } void solve(int N, int v) { n = N; if(n == 1) { answer({1}); return; } sz = 1 << (__lg(n - 1) + 1); vector<int> a(sz); for(int i = 0; i < sz; i++) a[i] = i + 1; int dep = bitonic(0, sz - 1, 1, 0, 0); assert(dep < MAXN); for(int j = 0; j < MAXN; j ++) { if(ops[j].empty()) continue; for(auto [x, y] : ops[j]) if(a[x] <= n && a[y] <= n) schedule(a[x], a[y]); vector<int> ret = visit(); int cnt = 0; for(auto [x, y] : ops[j]) { if(a[x] > n) continue; if(a[y] > n) { swap(a[x], a[y]); continue; } if (ret[cnt]) swap(a[x], a[y]); cnt ++; } } while(a.size() > n) a.pop_back(); answer(a); }

Compilation message (stderr)

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |         for(auto [x, y] : ops[j])
      |                  ^
swaps.cpp:55:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         for(auto [x, y] : ops[j])
      |                  ^
swaps.cpp:69:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     while(a.size() > n)
      |           ~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...