QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#304895#8004. Bit Componentucup-team1134#AC ✓11ms4644kbC++236.1kb2024-01-14 05:22:272024-01-14 05:22:28

Judging History

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

  • [2024-01-14 05:22:28]
  • 评测
  • 测评结果:AC
  • 用时:11ms
  • 内存:4644kb
  • [2024-01-14 05:22:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;

//Union Find


struct UF{
    int n;
    vector<int> par,size,edge;
    
    void init(int n_){
        n=n_;
        par.assign(n,-1);
        size.assign(n,1);
        edge.assign(n,0);
        
        for(int i=0;i<n;i++){
            par[i]=i;
        }
    }
    
    int root(int a){
        if(par[a]==a) return a;
        else return par[a]=root(par[a]);
    }
    
    void unite(int a,int b){
        edge[root(a)]++;
        if(root(a)!=root(b)){
            size[root(a)]+=size[root(b)];
            edge[root(a)]+=edge[root(b)];
            par[root(b)]=root(a);
        }
    }
    
    bool check(int a,int b){
        return root(a)==root(b);
    }
};

void check(vector<int> P){
    return;
    int N=si(P);
    vector<vector<int>> S(N,vector<int>(20));
    for(int i=0;i<N;i++){
        for(int j=0;j<20;j++){
            if(P[i]&(1<<j)) S[i][j]=1;
        }
    }
    UF uf;uf.init(N*20);
    for(int i=0;i<N;i++){
        for(int j=0;j<20;j++){
            if(i+1<N){
                if(S[i][j]&&S[i+1][j]) uf.unite(i*20+j,(i+1)*20+j);
            }
            if(j+1<20){
                if(S[i][j]&&S[i][j+1]) uf.unite(i*20+j,i*20+(j+1));
            }
        }
    }
    set<int> RO;
    for(int i=0;i<N;i++){
        cout<<bitset<20>(P[i])<<endl;
        for(int j=0;j<20;j++){
            if(S[i][j]){
                RO.insert(uf.root(i*20+j));
            }
        }
    }
    assert(si(RO)==1);
}

vector<int> make(int N){
    if(N==1) return {1};
    if(N==3) return {1,3,2};
    if(N==7) return {1,3,2,6,4,5,7};
    vector<int> X={1,3,2,6,4,5,7};
    for(int n=8;n<=400000;n*=2){
        vector<int> Y=X;
        for(int x:Y){
            X.push_back(x|n);
            if(X.back()==n+(n/2)) X.push_back(n);
        }
        
        if(si(X)==N){
            return X;
        }
    }
    return {};
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    if(N==1){
        cout<<"YES\n";
        cout<<1<<"\n";
        return 0;
    }
    if(N==3){
        cout<<"YES\n";
        cout<<"2 3 1\n";
        return 0;
    }
    if(N==13){
        vector<int> ans={1,3,2,6,4,5,7,13,9,11,10,8,12};
        cout<<"YES\n";
        for(int i=0;i<N;i++){
            if(i) cout<<" ";
            cout<<ans[i];
        }
        cout<<"\n";
        check(ans);
        return 0;
    }
    if(N==14){
        vector<int> ans={1,3,2,6,4,5,7,13,9,11,10,8,12,14};
        cout<<"YES\n";
        for(int i=0;i<N;i++){
            if(i) cout<<" ";
            cout<<ans[i];
        }
        cout<<"\n";
        check(ans);
        return 0;
    }
    if(N==15){
        vector<int> ans={1,3,2,6,4,5,7,13,9,11,10,8,12,14,15};
        cout<<"YES\n";
        for(int i=0;i<N;i++){
            if(i) cout<<" ";
            cout<<ans[i];
        }
        cout<<"\n";
        check(ans);
        return 0;
    }
    int k;
    for(int s=30;s>=0;s--){
        if(N&(1<<s)){
            k=s;
            break;
        }
    }
    if(!(N&(1<<(k-1)))){
        cout<<"NO\n";
        return 0;
    }
    if(N==((1<<k)+(1<<(k-1)))){
        cout<<"NO\n";
        return 0;
    }
    if(N==((1<<(k+1))-1)){
        auto re=make(N);
        cout<<"YES\n";
        for(int i=0;i<N;i++){
            if(i) cout<<" ";
            cout<<re[i];
        }
        cout<<"\n";
        return 0;
    }
    
    auto ans=make((1<<k)-1),Z=make((1<<(k-1))-1);
    
    for(int x:Z){
        if(x+(1<<k)+(1<<(k-1))<=N) ans.push_back(x+(1<<k)+(1<<(k-1)));
        ans.push_back(x+(1<<k));
        //cout<<x<<endl;
    }
    
    ans.push_back(1<<k);
    
    ans.push_back((1<<k)+(1<<(k-1)));
    
    cout<<"YES\n";
    for(int i=0;i<N;i++){
        if(i) cout<<" ";
        cout<<ans[i];
    }
    cout<<"\n";
    
    //check(ans);
    
    return 0;
    
    /*
    vector<int> X={1};
    for(int n=2;n<=400000;n*=2){
        vector<int> Y=X;reverse(all(Y));
        for(int x:Y){
            X.push_back(x|n);
        }
        X.push_back(n);
        
        if(si(X)==N){
            cout<<"YES\n";
            for(int i=0;i<N;i++){
                if(i) cout<<" ";
                cout<<X[i];
            }
            cout<<"\n";
            return 0;
        }
    }
    
    cout<<"NO\n";
    
    for(int N=25;N<=25;N++){
        vector<int> P(N);iota(all(P),1);
        do{
            vector<vector<int>> S(N,vector<int>(4));
            for(int i=0;i<N;i++){
                for(int j=0;j<4;j++){
                    if(P[i]&(1<<j)) S[i][j]=1;
                }
            }
            UF uf;uf.init(N*4);
            for(int i=0;i<N;i++){
                for(int j=0;j<4;j++){
                    if(i+1<N){
                        if(S[i][j]&&S[i+1][j]) uf.unite(i*4+j,(i+1)*4+j);
                    }
                    if(j+1<4){
                        if(S[i][j]&&S[i][j+1]) uf.unite(i*4+j,i*4+(j+1));
                    }
                }
            }
            set<int> RO;
            for(int i=0;i<N;i++){
                for(int j=0;j<4;j++){
                    if(S[i][j]){
                        RO.insert(uf.root(i*4+j));
                    }
                }
            }
            if(si(RO)==1){
                for(int i=0;i<N;i++){
                    for(int j=3;j>=0;j--){
                        cout<<S[i][j];
                    }
                    cout<<endl;
                }
                cout<<endl;
            }
        }while(next_permutation(all(P)));
    }
     */
}


这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3568kb

input:

1

output:

YES
1

result:

ok answer is 1

Test #2:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

2

output:

NO

result:

ok answer is 0

Test #3:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

3

output:

YES
2 3 1

result:

ok answer is 1

Test #4:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

4

output:

NO

result:

ok answer is 0

Test #5:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

5

output:

NO

result:

ok answer is 0

Test #6:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

6

output:

NO

result:

ok answer is 0

Test #7:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

7

output:

YES
1 3 2 6 4 5 7

result:

ok answer is 1

Test #8:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

8

output:

NO

result:

ok answer is 0

Test #9:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

9

output:

NO

result:

ok answer is 0

Test #10:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

10

output:

NO

result:

ok answer is 0

Test #11:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

11

output:

NO

result:

ok answer is 0

Test #12:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

12

output:

NO

result:

ok answer is 0

Test #13:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

13

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12

result:

ok answer is 1

Test #14:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

14

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14

result:

ok answer is 1

Test #15:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

15

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15

result:

ok answer is 1

Test #16:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

16

output:

NO

result:

ok answer is 0

Test #17:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

17

output:

NO

result:

ok answer is 0

Test #18:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

23

output:

NO

result:

ok answer is 0

Test #19:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

24

output:

NO

result:

ok answer is 0

Test #20:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

25

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 25 17 19 18 22 20 21 23 16 24

result:

ok answer is 1

Test #21:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

26

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 25 17 19 26 18 22 20 21 23 16 24

result:

ok answer is 1

Test #22:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

27

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 25 17 27 19 26 18 22 20 21 23 16 24

result:

ok answer is 1

Test #23:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

40

output:

NO

result:

ok answer is 0

Test #24:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

53

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 49 33 51 35 50 34 38 52 36 53 37 39 41 43 42 46 44 40 45 47 32 48

result:

ok answer is 1

Test #25:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

93

output:

NO

result:

ok answer is 0

Test #26:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

105

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 97 65 99 67 98 66 102 70 100 68 101 69 103 71 105 73 75 74 78 76 104 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88...

result:

ok answer is 1

Test #27:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

132

output:

NO

result:

ok answer is 0

Test #28:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

221

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #29:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

373

output:

NO

result:

ok answer is 0

Test #30:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

473

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #31:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

513

output:

NO

result:

ok answer is 0

Test #32:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

934

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #33:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

1356

output:

NO

result:

ok answer is 0

Test #34:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

1651

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #35:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

2263

output:

NO

result:

ok answer is 0

Test #36:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

3330

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #37:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

4375

output:

NO

result:

ok answer is 0

Test #38:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

7989

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #39:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

10925

output:

NO

result:

ok answer is 0

Test #40:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

14097

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #41:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

16893

output:

NO

result:

ok answer is 0

Test #42:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

28913

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #43:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

40092

output:

NO

result:

ok answer is 0

Test #44:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

54980

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #45:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

88104

output:

NO

result:

ok answer is 0

Test #46:

score: 0
Accepted
time: 11ms
memory: 3812kb

input:

106284

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #47:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

152797

output:

NO

result:

ok answer is 0

Test #48:

score: 0
Accepted
time: 8ms
memory: 4644kb

input:

200000

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #49:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

3073

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #50:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

16383

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #51:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

32767

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #52:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

399

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Test #53:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

5757

output:

NO

result:

ok answer is 0

Test #54:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

179

output:

NO

result:

ok answer is 0

Test #55:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

228

output:

YES
1 3 2 6 4 5 7 9 11 10 14 12 8 13 15 17 19 18 22 20 21 23 25 27 26 30 28 24 16 29 31 33 35 34 38 36 37 39 41 43 42 46 44 40 45 47 49 51 50 54 52 53 55 57 59 58 62 60 56 48 32 61 63 65 67 66 70 68 69 71 73 75 74 78 76 72 77 79 81 83 82 86 84 85 87 89 91 90 94 92 88 80 93 95 97 99 98 102 100 101 10...

result:

ok answer is 1

Extra Test:

score: 0
Extra Test Passed