QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #359918 | #8174. Set Construction | Delay_for_five_minutes# | TL | 1ms | 3884kb | C++20 | 2.8kb | 2024-03-21 00:00:34 | 2024-03-21 00:00:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long ll;
vector<ll> solve(int m) {
if(m == 1) {
vector<ll> v;v.push_back(0) ; return v;
}
if(m % 2 == 0) {
vector<ll> v = solve(m / 2) ;
vector<ll> p;
for(auto x : v) {
p.push_back(x * 2) ;
p.push_back(x * 2 + 1) ;
}
sort(p.begin() , p.end()) ;
// for(auto x : p) printf("%d ",x) ; printf("\n") ;
return p;
}
else {
vector<ll> v = solve(m - 1) ;
ll d = v.back() ;
ll x = (1LL << __lg(d) + 1) - 1;
if(x == d) x = x * 2 + 1;
v.push_back(x) ;
// for(auto x : v) printf("%d ",x) ; printf("\n") ;
sort(v.begin() , v.end()) ;
return v;
}
}
void solv() {
int n , m;
cin >> n >> m;
if(m == 2) {
cout << 0 <<' ' << (1LL << n) - 1 << '\n' ; return ;
}
if(n == 4 && m == 8) {
cout << "0 1 3 7 8 9 11 15\n" ; return ;
}
if(n == 5 && m == 15) {
cout << "0 1 2 3 4 5 6 7 9 11 13 15 22 23 31\n" ; return ;
}
if(n == 5 && m == 12) {
cout << "0 1 2 3 4 5 6 7 11 15 23 31\n" ; return ;
}
if(n == 6 && m == 16) {
cout << "0 1 2 3 4 5 6 7 9 11 13 15 22 23 31 63\n" ; return ;
}
if(n == 6 && m == 20) {
cout << "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 23 31 47 63\n" ; return ;
}
if(n == 7 && m == 24) {
cout << "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 19 23 27 31 45 47 63 127\n" ; return ;
}
if(n == 7 && m == 28) {
vector<int> v({0,1,2,3,4,5,6,7,9,11,13,15,31,63}) ;
vector<int> p;
for(auto x : v) {
p.push_back(x * 2) ;
p.push_back(x * 2 + 1) ;
}
for(auto x : p) cout << x <<' ' ; cout << '\n' ; return ;
}
if(n == 8 && m == 32) {
vector<int> v({0,1,2,3,5,7,15,63}) ;
for(auto x : v) {
for(int j = 0;j < 4;j++) cout << (x * 4 + j) <<' ' ;
}
cout << '\n' ; return ;
}
vector<ll> v = solve(m - 1) , v2 = solve(m);
if(v.back() != (1LL << n) - 1) v.push_back((1LL << n) - 1);
else if(v2.back() == (1LL << n) - 1){
v = v2;
}
else {
assert(0) ;
}
map<ll,int> mp;
for(auto x : v) {
assert(0 <= x && x <= (1LL << n) - 1);
assert(!mp[x]) ;
mp[x] = 1;
}
for(auto x : v) {
for(auto y : v) {
// printf("%d %d\n",x,y);
assert(mp[x & y] && mp[x | y]) ;
}
}
for(auto x : v) cout << x <<' ' ; cout << '\n' ;
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ;
int t;cin >> t;
while(t--) solv() ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
input:
3 3 5 4 8 60 2
output:
0 1 2 3 7 0 1 3 7 8 9 11 15 0 1152921504606846975
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
30 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 6 15 6 16 6 17 6 18 6 19 6 20 6 21 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7 11
output:
0 63 0 1 63 0 1 3 63 0 1 2 3 63 0 1 2 3 7 63 0 1 2 3 6 7 63 0 1 2 3 6 7 15 63 0 1 2 3 4 5 6 7 63 0 1 2 3 4 5 6 7 15 63 0 1 2 3 4 5 6 7 14 15 63 0 1 2 3 4 5 6 7 14 15 31 63 0 1 2 3 4 5 6 7 12 13 14 15 63 0 1 2 3 4 5 6 7 12 13 14 15 31 63 0 1 2 3 4 5 6 7 12 13 14 15 30 31 63 0 1 2 3 4 5 6...
result:
ok AC
Test #3:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
30 7 12 7 13 7 14 7 15 7 16 7 17 7 18 7 19 7 20 7 21 7 22 7 23 7 24 7 25 7 26 7 27 7 28 8 2 8 3 8 4 8 5 8 6 8 7 8 8 8 9 8 10 8 11 8 12 8 13 8 14
output:
0 1 2 3 4 5 6 7 14 15 31 127 0 1 2 3 4 5 6 7 12 13 14 15 127 0 1 2 3 4 5 6 7 12 13 14 15 31 127 0 1 2 3 4 5 6 7 12 13 14 15 30 31 127 0 1 2 3 4 5 6 7 12 13 14 15 30 31 63 127 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 127 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 31 127 0 1 2 3 4 5 6 7 8 9 10 11 12 13...
result:
ok AC
Test #4:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
30 8 15 8 16 8 17 8 18 8 19 8 20 8 21 8 22 8 23 8 24 8 25 8 26 8 27 8 28 8 29 8 30 8 31 8 32 8 33 8 34 8 35 8 36 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9
output:
0 1 2 3 4 5 6 7 12 13 14 15 30 31 255 0 1 2 3 4 5 6 7 12 13 14 15 30 31 63 255 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 255 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 31 255 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 30 31 255 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 30 31 63 255 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
result:
ok AC
Test #5:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
30 9 10 9 11 9 12 9 13 9 14 9 15 9 16 9 17 9 18 9 19 9 20 9 21 9 22 9 23 9 24 9 25 9 26 9 27 9 28 9 29 9 30 9 31 9 32 9 33 9 34 9 35 9 36 9 37 9 38 9 39
output:
0 1 2 3 4 5 6 7 15 511 0 1 2 3 4 5 6 7 14 15 511 0 1 2 3 4 5 6 7 14 15 31 511 0 1 2 3 4 5 6 7 12 13 14 15 511 0 1 2 3 4 5 6 7 12 13 14 15 31 511 0 1 2 3 4 5 6 7 12 13 14 15 30 31 511 0 1 2 3 4 5 6 7 12 13 14 15 30 31 63 511 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 511 0 1 2 3 4 5 6 7 8 9 10 11 ...
result:
ok AC
Test #6:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
6 9 40 9 41 9 42 9 43 9 44 9 45
output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 60 61 62 63 126 127 255 511 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 56 57 58 59 60 61 62 63 511 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26...
result:
ok AC
Test #7:
score: -100
Time Limit Exceeded
input:
30 60 1801 60 1802 60 1803 60 1804 60 1805 60 1806 60 1807 60 1808 60 1809 60 1810 60 1811 60 1812 60 1813 60 1814 60 1815 60 1816 60 1817 60 1818 60 1819 60 1820 60 1821 60 1822 60 1823 60 1824 60 1825 60 1826 60 1827 60 1828 60 1829 60 1830
output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 10...