# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
905251 | Ahmed57 | The Collection Game (BOI21_swaps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#include "swaps.h"
int a[2001] = {0};
int n;
vector<int> nah;
/*void schedule(int a,int b){
if(rea[a]>rea[b]){
nah.push_back(1);
}else nah.push_back(0);
}*/
int x = 0;
void compp(int a,int b){
if(b<=n&&a<=n){
schedule(a,b);
x++;
}
}/*
vector<int> visit(){
vector<int> xdd = nah;
nah.clear();
return xdd;
}*/
void bitonic(int l, int r, bool inc){
if(l==r)return ;
int md=(l+r)/2;
bitonic(l,md,inc);
bitonic(md+1,r,!inc);
vector<int> vi;
for(int i = l;i<=md;i++){
compp(a[i],a[i+md+1-l]);
}
vi = visit();
if(vi.size()!=x){
assert();
}
x = 0;
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((!inc)^(!vi[ind])){
swap(a[i],a[i+(md+1-l)]);
}
ind++;
}
}
bitonic(l,md,inc);
bitonic(md+1,r,inc);
}
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;
}
bitonic(1,xd,1);
vector<int> ans;
for(int i = xd-N+1;i<=xd;i++){
ans.push_back(a[i]);
}
answer(ans);
}/*
int main(){
freopen("input.txt","r",stdin);
freopen("outout.txt","w",stdout);
rea[1] = 4, rea[2] = 1, rea[3] = 2 , rea[4] = 3 , rea[5] = 10;
a[1] =1 , a[2] = 2 , a[3] = 3 , a[4] = 4 , a[5] = 5 , a[6] = 6, a[7] = 7 , a[8] = 8;
n = 5;
bitonic(1,8,1);
for(int i = 1;i<=8;i++){
cout<<a[i]<<" ";
}
}*/