QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #306660 | #8004. Bit Component | ucup-team228 | WA | 8ms | 13416kb | C++20 | 2.0kb | 2024-01-16 23:50:48 | 2024-01-16 23:50:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int K = 20;
vector<int> mem[K];
void precalc() {
mem[1] = {1};
mem[2] = {2, 3, 1};
mem[3] = {7, 5, 4, 6, 2, 3, 1};
for (int k = 3; k + 1 < K; k++) {
mem[k + 1].push_back((1 << k) + (1 << (k - 1)));
mem[k + 1].push_back((1 << k));
for (int x : mem[k - 1]) {
mem[k + 1].push_back(x + (1 << k));
}
mem[k + 1].push_back((1 << k) + (1 << (k - 1)) + 1);
for (int x : mem[k]) {
mem[k + 1].push_back(x);
}
vector<int> cur;
cur.push_back((1 << (k + 1)) - 1);
for (int x : mem[k + 1]) {
cur.push_back(x);
if (x >= (1 << k) + 1 && (1 << (k - 1)) + x <= (1 << (k + 1)) - 2) {
cur.push_back(x + (1 << (k - 1)));
}
}
swap(cur, mem[k + 1]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
precalc();
int n;
cin >> n;
int k = 0;
while ((1 << (k + 1)) <= n) {
k++;
}
if (n == 1) {
cout << "YES\n";
cout << "1\n";
} else if (n == 2) {
cout << "NO\n";
} else if (n == 3) {
cout << "YES\n";
cout << "2 3 1\n";
} else {
if (n <= 6) {
cout << "NO\n";
} else if (n == 7) {
cout << "YES\n";
for (int x : mem[3]) {
cout << x << " ";
}
cout << "\n";
} else if (n <= (1 << k) + (1 << (k - 1))) {
cout << "NO\n";
} else {
cout << "YES\n";
for (int x : mem[k + 1]) {
if (x <= n) {
cout << x << " ";
}
}
cout << "\n";
}
}
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11732kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 11808kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 12024kb
input:
3
output:
YES 2 3 1
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 12128kb
input:
4
output:
NO
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 11740kb
input:
5
output:
NO
result:
ok answer is 0
Test #6:
score: 0
Accepted
time: 2ms
memory: 11888kb
input:
6
output:
NO
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 0ms
memory: 12156kb
input:
7
output:
YES 7 5 4 6 2 3 1
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 4ms
memory: 11948kb
input:
8
output:
NO
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 4ms
memory: 13128kb
input:
9
output:
NO
result:
ok answer is 0
Test #10:
score: 0
Accepted
time: 8ms
memory: 11564kb
input:
10
output:
NO
result:
ok answer is 0
Test #11:
score: 0
Accepted
time: 0ms
memory: 13416kb
input:
11
output:
NO
result:
ok answer is 0
Test #12:
score: 0
Accepted
time: 8ms
memory: 12352kb
input:
12
output:
NO
result:
ok answer is 0
Test #13:
score: -100
Wrong Answer
time: 8ms
memory: 12072kb
input:
13
output:
YES 12 8 10 11 9 13 13 7 5 4 6 2 3 1
result:
wrong answer Every number must appear exactly once, but 1 appears 0 times