QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #359914 | #8174. Set Construction | Delay_for_five_minutes# | WA | 0ms | 3584kb | C++20 | 1.8kb | 2024-03-20 23:44:08 | 2024-03-20 23:44:08 |
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) ;
int d = v.back() ;
int x = (1 << __lg(d) + 1) - 1;
if(x == d) x = x * 2 + 1;
v.push_back(x) ;
// for(auto x : v) printf("%d ",x) ; printf("\n") ;
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 ;
}
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: 3584kb
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: -100
Wrong Answer
time: 0ms
memory: 3580kb
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:
wrong answer 63 is not in A