QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#586950 | #8004. Bit Component | ucup-team3519# | WA | 2ms | 3548kb | C++20 | 1.9kb | 2024-09-24 16:44:37 | 2024-09-24 16:44:39 |
Judging History
answer
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=500005;
const ll mod=998244353;
int G(int x){
return x^(x>>1);
}
vector<int>ans7={7,5,4,6,2,3,1};
vector<int>ans;
vector<int>follow[N];
void fill(int carry,int l,int r){
if(l<=r){
for(int i=l;i<=r;i++){
ans.push_back(carry^G(i));
}
}
else{
for(int i=l;i>=r;i--){
ans.push_back(carry^G(i));
}
}
}
void op(int x){
vector<int>rlans;
if(x==0){
cout<<"NO\n";
return;
}
cout<<"YES\n";
for(int i=0;i<ans.size();i++){
ll p=ans[i];
// cout<<p<<' ';
rlans.push_back(p);
for(int j=0;j<follow[p].size();j++){
rlans.push_back(follow[p][j]);
//cout<<follow[p][j]<<' ';
}
}
// cout<<rlans.size()<<'\n';
for(int i=0;i<rlans.size();i++){
// for(int j=10;j>=0;j--){
// if(rlans[i]&(1<<j)){
// cout<<1;
// }
// else{
// cout<<0;
// }
// }
// cout<<'\n';
cout<<rlans[i]<<' ';
}
return;
}
void solve(){
int n;
cin>>n;
if(n<=7){
if(n==1){
ans={1};
op(1);
}
else if(n==3){
op(1);
}
else if(n==7){
ans=ans7;
op(1);
}
else{
op(0);
}
return;
}
ll lb;
for(int i=20;i>=0;i--){
if(n&(1<<i)){
lb=i;
break;
}
}
if(!(n&(1<<(lb-1)))){
op(0);
return;
}
if(n==(1<<lb)+(1<<(lb-1))){
op(0);
return;
}
for(int i=3;i<=lb;i++){
ans.push_back((1<<i)+(1<<(i-1)));
ans.push_back(1<<i);
}
fill(1<<lb,(1<<(lb-1))-1,1);
for(int i=(1<<lb)+(1<<(lb-1))+2;i<=n;i++){
follow[i-(1<<(lb-1))].push_back(i);
}
ans.push_back((1<<lb)+(1<<(lb-1))+1);
for(int b=lb-1;b>=3;b--){
fill((1<<b),1,(1<<b)-2);
// follow[(1<<b)].push_back((1<<b)+(1<<(b-1)));
}
for(int i=0;i<7;i++){
ans.push_back(ans7[i]);
}
op(1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3548kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3548kb
input:
3
output:
YES
result:
wrong output format Unexpected end of file - int32 expected