Submission #905296

#TimeUsernameProblemLanguageResultExecution timeMemory
905296Ahmed57The Collection Game (BOI21_swaps)C++17
100 / 100
6 ms3700 KiB
#include <bits/stdc++.h> using namespace std; #include "swaps.h" int a[2001] = {0}; vector<array<int,3>> v[100001]; int n;int lel =0; vector<int> nah; void comp(int a,int b){ if(b<=n&&a<=n){ schedule(a,b); } } int bitonic(int l, int r, bool inc , bool all ,int lvl){ if(l==r)return lvl-1; int md=(l+r)/2; int ma = lvl-1; if(all){ ma = bitonic(l,md,inc,1,lvl); bitonic(md+1,r,!inc,1,lvl); } lel++; vector<int> vi; for(int i = l;i<=md;i++){ v[ma+1].push_back({i,i+md+1-l,inc}); //comp(a[i],a[i+md+1-l]); } /*vi = visit(); int ind = 0; for(int i = l;i<=md;i++){ if(a[i+md+1-l]>n){ if(inc){ swap(a[i],a[i+(md+1-l)]); } }else if(a[i]>n){ if(!inc){ swap(a[i],a[i+(md+1-l)]); } }else{ if(ind>=vi.size()){ assert(0); } if((!inc)^(!vi[ind])){ swap(a[i],a[i+(md+1-l)]); } ind++; } }*/ bitonic(l,md,inc,0,ma+2); return bitonic(md+1,r,inc,0,ma+2); } void solve(int N,int V){ n = N; int xd = 1; while(xd<N)xd*=2; for(int i = 1;i<=xd;i++){ a[i] = i; } int ma = bitonic(1,xd,1,1,0); for(int i = 0;i<=ma;i++){ for(auto j:v[i]){ comp(a[j[0]],a[j[1]]); } vector<int> vi = visit(); int ind = 0; for(auto j:v[i]){ if(a[j[1]]>n){ if(j[2]){ swap(a[j[0]],a[j[1]]); } }else if(a[j[0]]>n){ if(!j[2]){ swap(a[j[0]],a[j[1]]); } }else{ if(ind>=vi.size()){ assert(0); } if((!j[2])^(!vi[ind])){ swap(a[j[0]],a[j[1]]); } ind++; } } } vector<int> ans; for(int i = xd-N+1;i<=xd;i++){ ans.push_back(a[i]); } answer(ans); }

Compilation message (stderr)

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                 if(ind>=vi.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...