QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#438528 | #8004. Bit Component | real_sigma_team# | WA | 1ms | 3824kb | C++23 | 1.6kb | 2024-06-10 19:10:44 | 2024-06-10 19:10:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int rev(int x, int k) {
vector<int> bit;
for (int i = 0; i < k; ++i)
bit.push_back(bool((1 << i) & x));
reverse(bit.begin(), bit.end());
int y = 0;
for (int i = 0; i < k; ++i)
if (bit[i])
y += (1 << i);
return y;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
int k = __lg(n);
if (n <= (1 << k) + (1 << (k - 1))) {
cout << "NO";
return 0;
}
cout << "YES\n";
if (n == 1) {
cout << "1";
return 0;
}
if (n == 3) {
cout << "2 3 1";
return 0;
}
if (n == 7) {
cout << "7 5 1 3 2 6 4";
return 0;
}
vector<vector<int>> solve(k + 2);
solve[2] = {1, 3, 2};
solve[3] = {7, 5, 1, 3, 2, 6, 4};
for (int i = 4; i <= k + 1; ++i) {
solve[i].push_back((1 << i) - 1);
for (int j: solve[i - 2]) {
solve[i].push_back(rev(j, i - 2) + (1 << (i - 1)));
if (rev(j, i - 2) != 1 && rev(j, i - 2) + (1 << (i - 1)) + (1 << (i - 2)) != (1 << i) - 1)
solve[i].push_back(rev(j, i - 2) + (1 << (i - 1)) + (1 << (i - 2)));
}
solve[i].push_back((1 << (i - 1)) + (1 << (i - 2)) + 1);
for (int j: solve[i - 1])
solve[i].push_back(j);
solve[i].push_back((1 << (i - 1)) + (1 << (i - 2)));
solve[i].push_back((1 << (i - 1)));
}
for (int i: solve[k + 1])
if (i <= n)
cout << i << ' ';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3520kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3652kb
input:
3
output:
NO
result:
wrong answer Jury has the answer, participant doesn't