QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#304617 | #8004. Bit Component | ucup-team1631# | WA | 1ms | 3500kb | C++17 | 2.7kb | 2024-01-13 21:55:38 | 2024-01-13 21:55:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define elif else if
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int,int>
#define repname(a, b, c, d, e, ...) e
#define rep(...) repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rep0(x) for (int rep_counter = 0; rep_counter < (x); ++rep_counter)
#define rep1(i, x) for (int i = 0; i < (x); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rep3(i, l, r, c) for (int i = (l); i < (r); i += (c))
struct ScalarInput {
template<class T>
operator T(){
T ret;
cin >> ret;
return ret;
}
};
struct VectorInput {
size_t n;
VectorInput(size_t n): n(n) {}
template<class T>
operator vector<T>(){
vector<T> ret(n);
for(T &x : ret) cin >> x;
return ret;
}
};
ScalarInput input(){ return ScalarInput(); }
VectorInput input(size_t n){ return VectorInput(n); }
template<typename T>
void print(vector<T> a){
for(int i=0;i<a.size();i++){
cout<<a[i]<<" \n"[i+1==a.size()];
}
}
template<class T>
void print(T x){
cout << x << '\n';
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail){
cout << head << ' ';
print(forward<Tail>(tail)...);
}
vector<int> make(int n);
vector<int> make2(int n);
vector<int> make(int n){
// n = 110000000...0001
assert(n>=7);
int B=0;
while((1<<B)<=n){
B+=1;
}
assert(n==((1<<(B-1)))+(1<<(B-2))+1);
if(n==7){
return {1, 3, 2, 6, 4, 5, 7};
}
vector<int>A=make2((1<<(B-1))-1);
A.push_back(n);
vector<int>C=make2((1<<(B-2))-1);
rep(i,C.size()){
A.push_back(C[i]+(1<<(B-1)));
}
A.push_back((1<<(B-1))+(1<<(B-2)));
return A;
}
vector<int>make2(int n){
// n=11111111
int B=0;
while((1<<B)<=n){
B+=1;
}
if(n==1){
return {1};
}
if(n==3){
return {1,3,2};
}
if(n==7){
return {1, 3, 2, 6, 4, 5, 7};
}
if(n<7){
print("NO");
return {};
}
int N=(1<<(B-1))+(1<<(B-2))+1;
if(n<N){
print("NO");
return {};
}
vector<int>A=make(N);
vector<int>C;
int L=1<<(B-2);
int R=1<<(B-1);
rep(i,N-1){
C.push_back(A[i]);
if(A[i]!=((1<<(B-1))-1)){
if((L<=A[i])&&(A[i]<R)&&(A[i]+(1<<(B-1)))<=n){
C.push_back(A[i]+(1<<(B-1)));
}
}
}
if(((1<<B)-1)==n){
C.push_back((1<<B)-1);
}
return C;
}
int main(){
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
int n;
cin>>n;
vector<int> ans=make2(n);
if((int)ans.size()!=0){
print("YES");
print(ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3424kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
3
output:
YES 1 3 2
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
4
output:
NO
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
5
output:
NO
result:
ok answer is 0
Test #6:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
6
output:
NO
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
7
output:
YES 1 3 2 6 4 5 7
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
8
output:
NO
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
9
output:
NO
result:
ok answer is 0
Test #10:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
10
output:
NO
result:
ok answer is 0
Test #11:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
11
output:
NO
result:
ok answer is 0
Test #12:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
12
output:
NO
result:
ok answer is 0
Test #13:
score: -100
Wrong Answer
time: 1ms
memory: 3428kb
input:
13
output:
YES 1 3 2 6 4 12 5 13 7 13 9 11 10 12
result:
wrong answer Every number must appear exactly once, but 8 appears 0 times