QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#304895 | #8004. Bit Component | ucup-team1134# | AC ✓ | 11ms | 4644kb | C++23 | 6.1kb | 2024-01-14 05:22:27 | 2024-01-14 05:22:28 |
Judging History
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