# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
735445 | keisuke6 | Fun Tour (APIO20_fun) | C++14 | 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;
#define int long long
signed main(){
int N;
cin>>N;
vector<int> A = {};
while(N > 2){
int d = 0;
while((1<<(d+1)) <= N) d++;
if(N+1-(1<<d) > (1<<(d-1))){
int s = (1<<d)+(1<<(d+1))-3;
int c = 0;
for(int i=(1<<d)-1;i<(1<<d)-1+(1<<(d-1));i++)if(s-i < N && i < s-i){
A.push_back(s-i);
A.push_back(i);
c += 2;
}
N -= c;
continue;
}
if(N+1-(1<<d) > (1<<(d-1)-1)/2+1){
int s = (1<<d)+(1<<d)+(1<<(d-1))-3;
int c = 0;
for(int i=(1<<d)-1;i<=s-((1<<d)-1);i++)if(s-i < N && i < s-i){
A.push_back(i);
A.push_back(s-i);
c+=2;
}
N -= c;
continue;
}
int c = 0;
for(int i=(1<<d)-1;i<N;i++){
c += 2;
A.push_back((1<<(d+1))-3-i);
A.push_back(i);
}
N -= c;
if(clock()*1.0/CLOCKS_PER_SEC > 1.6) break;
}
if(N == 2){
A.push_back(1);
A.push_back(0);
}
if(N == 1) A.push_back(0);
for(int x:A) cout<<x<<' ';
cout<<endl;
}