Submission #858109

#TimeUsernameProblemLanguageResultExecution timeMemory
858109lovrotThe Collection Game (BOI21_swaps)C++17
100 / 100
4 ms1688 KiB
#include "swaps.h" #include <cstdio> #include <algorithm> #include <vector> #include <cassert> #define EB emplace_back #define X first #define Y second #define MP make_pair using namespace std; typedef pair<int, int> pii; void solve(int n, int v) { int m = 1; vector<int> ANS; for(; m < n; m <<= 1) {} for(int i = 0; i < m; ++i) ANS.EB(i + 1); for(int i = 1 << 1; i <= m; i <<= 1) for(int j = i >> 1; j; j >>= 1) { vector<pii> S; for(int k = 0; k < m; ++k) { int _k = k, l = k ^ j; if(l > _k) { if(_k & i) swap(l, _k); S.EB(MP(_k, l)); // printf("sche %d[%d] %d[%d]\n", ANS[_k], _k, ANS[l], l); if(ANS[_k] <= n && ANS[l] <= n) schedule(ANS[_k], ANS[l]); } } vector<int> RES = visit(); for(int k = 0, cnt = 0; k < S.size(); ++k) { int a = S[k].X, b = S[k].Y; if(ANS[a] <= n && ANS[b] <= n) { assert(cnt < RES.size()); if(!RES[cnt]) swap(ANS[a], ANS[b]); ++cnt; } else if(ANS[a] > n && ANS[b] <= n) { swap(ANS[a], ANS[b]); } } S.clear(); } // for(int i = 0; i < m; ++i) printf("%d%c", ANS[i], " \n"[i == m - 1]); for(int i = 0; i < m - n; ++i) ANS.pop_back(); answer(ANS); } /* for(int i = 0, j = 0; i < RES.size(); ++i) { if(!RES[i]) swap(ANS[S[i].X], ANS[S[i].Y]); } */

Compilation message (stderr)

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:36:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int k = 0, cnt = 0; k < S.size(); ++k) {
      |                            ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from swaps.cpp:5:
swaps.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |      assert(cnt < RES.size());
      |             ~~~~^~~~~~~~~~~~
#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...