QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#304617#8004. Bit Componentucup-team1631#WA 1ms3500kbC++172.7kb2024-01-13 21:55:382024-01-13 21:55:38

Judging History

你现在查看的是最新测评结果

  • [2024-01-13 21:55:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3500kb
  • [2024-01-13 21:55:38]
  • 提交

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