QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #317294 | #8004. Bit Component | ucup-team2307# | AC ✓ | 3ms | 4144kb | C++20 | 3.1kb | 2024-01-28 19:47:59 | 2024-01-28 19:47:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
int p[100500];
int get(int v)
{
if (v == p[v])
return v;
return p[v] = get(p[v]);
}
void unite(int u, int v)
{
u = get(u);
v = get(v);
p[u] = v;
}
bool check(vector<int> v)
{
int n = v.size();
int k = 30;
for (int i=0; i<n*k; i++)
p[i] = i;
for (int i=0; i<n; i++)
for (int j=0; j+1<k; j++)
if ((v[i]>>j) & 1)
if ((v[i]>>(j+1)) & 1)
unite(k*i+j, k*i+j+1);
// for (int i=0; i<n; i++, cout<<"\n")
// for (int j=0; j<k; j++)
// cout<<get(k*i+j)<<" ";
for (int i=0; i+1<n; i++)
for (int j=0; j<k; j++)
if ((v[i]>>j)&1)
if ((v[i+1]>>j)&1)
unite(k*i+j, k*(i+1)+j);
// for (int i=0; i<n; i++, cout<<"\n")
// for (int j=0; j<k; j++)
// cout<<get(k*i+j)<<" ";
// for (int i=0; i<n; i++, cout<<"\n")
// for (int j=0; j<k; j++)
// cout<<((v[i]>>j)&1);
// for (int i=0; i<n; i++, cout<<"\n")
// for (int j=0; j<k; j++)
// cout<<get(k*i+j)<<" ";
set<int> st;
for (int i=0; i<n; i++)
for (int j=0; j<k; j++)
if ((v[i]>>j)&1)
{
st.insert(get(k*i+j));
if (st.size() > 1)
return false;
}
return true;
}
vector<int> solve(int n)
{
if(n==1)
return {0,1};
else if(n==2)
return {};
else if(n==3)
return {0,2,3,1};
int msb=31-__builtin_clz(n);
int pw=1<<(msb-1);
if(!(n&pw)||!(n&(pw-1)))
return {};
vector<int> ans{0,1,3,2,6,4,7,5};
vector<int> ans1{0,2,3,1};
for(int p=3;(1<<p)<=n;p++)
{
pw=1<<p;
int ones=(pw<<1)-1;
int init=pw|(pw>>1)|1;
ans.push_back(init);
for(int i=(pw>>1)-1;i>=0;i--)
{
int small=pw|(p==3?ans1:ans)[i];
ans.push_back(small);
int big=small|(pw>>1);
if(big<=n&&big!=ones&&big!=init)
ans.push_back(big);
}
if(ones<=n&&ones!=init)
ans.push_back(ones);
}
return ans;
// if(!check(ans))
// cout<<"BAD",exit(0);
// cout<<"YES\n";
// for(int i=1;i<=n;i++)
// cout<<ans[i]<<" ";
// for(int x:ans)
// cout<<x<<" ";
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
// for(int n=1;n<=1000;n++)
int n;
cin>>n;
{
auto ans=solve(n);
// if(!ans.empty()&&(ans.size()!=n+1||!check(ans)))
// cout<<"BAD",exit(0);
if(ans.empty())
cout<<"NO";
else
{
cout<<"YES\n";
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
}
}
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
3
output:
YES 2 3 1
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
4
output:
NO
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
5
output:
NO
result:
ok answer is 0
Test #6:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
6
output:
NO
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
7
output:
YES 1 3 2 6 4 7 5
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
8
output:
NO
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
9
output:
NO
result:
ok answer is 0
Test #10:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
10
output:
NO
result:
ok answer is 0
Test #11:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
11
output:
NO
result:
ok answer is 0
Test #12:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
12
output:
NO
result:
ok answer is 0
Test #13:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
13
output:
YES 1 3 2 6 4 7 5 13 9 11 10 8 12
result:
ok answer is 1
Test #14:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
14
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12
result:
ok answer is 1
Test #15:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
15
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15
result:
ok answer is 1
Test #16:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
16
output:
NO
result:
ok answer is 0
Test #17:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
17
output:
NO
result:
ok answer is 0
Test #18:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
23
output:
NO
result:
ok answer is 0
Test #19:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
24
output:
NO
result:
ok answer is 0
Test #20:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
25
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 23 20 22 18 19 17 16 24
result:
ok answer is 1
Test #21:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
26
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 23 20 22 18 26 19 17 16 24
result:
ok answer is 1
Test #22:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
27
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 23 20 22 18 26 19 27 17 16 24
result:
ok answer is 1
Test #23:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
40
output:
NO
result:
ok answer is 0
Test #24:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
53
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 40 46 42 43 41 45 37 53 39 36 52 38 34 50 35 51 33 32 48
result:
ok answer is 1
Test #25:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
93
output:
NO
result:
ok answer is 0
Test #26:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
105
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 80 81 91 83 90 82 94 86 92 84 87 93 85 89 79 76 72 104 78 74 75 73 105 77 69 101 71 103 68 100 70 102 66 98...
result:
ok answer is 1
Test #27:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
132
output:
NO
result:
ok answer is 0
Test #28:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
221
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #29:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
373
output:
NO
result:
ok answer is 0
Test #30:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
473
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #31:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
513
output:
NO
result:
ok answer is 0
Test #32:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
934
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #33:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1356
output:
NO
result:
ok answer is 0
Test #34:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1651
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #35:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
2263
output:
NO
result:
ok answer is 0
Test #36:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
3330
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #37:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4375
output:
NO
result:
ok answer is 0
Test #38:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
7989
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #39:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
10925
output:
NO
result:
ok answer is 0
Test #40:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
14097
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #41:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
16893
output:
NO
result:
ok answer is 0
Test #42:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
28913
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #43:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
40092
output:
NO
result:
ok answer is 0
Test #44:
score: 0
Accepted
time: 3ms
memory: 4012kb
input:
54980
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #45:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
88104
output:
NO
result:
ok answer is 0
Test #46:
score: 0
Accepted
time: 3ms
memory: 3796kb
input:
106284
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #47:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
152797
output:
NO
result:
ok answer is 0
Test #48:
score: 0
Accepted
time: 3ms
memory: 4144kb
input:
200000
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #49:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
3073
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #50:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
16383
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #51:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
32767
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #52:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
399
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Test #53:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
5757
output:
NO
result:
ok answer is 0
Test #54:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
179
output:
NO
result:
ok answer is 0
Test #55:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
228
output:
YES 1 3 2 6 4 7 5 13 9 11 10 14 8 12 15 25 21 29 23 20 28 22 30 18 26 19 27 17 16 24 31 49 47 44 60 40 56 46 62 42 58 43 59 41 57 45 61 37 53 39 55 36 52 38 54 34 50 35 51 33 32 48 63 97 95 88 120 80 112 81 113 91 123 83 115 90 122 82 114 94 126 86 118 92 124 84 116 87 119 93 125 85 117 89 121 79 11...
result:
ok answer is 1
Extra Test:
score: 0
Extra Test Passed