QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422424 | #8174. Set Construction | _qwqUwU | TL | 562ms | 4136kb | C++20 | 1.5kb | 2024-05-27 14:11:19 | 2024-05-27 14:11:19 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline ll read(){
ll x=0,c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0' && c<='9')x=x*10 + c-'0',c=getchar();
return x;
}
int n,m;
#define lb(s) (s&-s)
#define pnp(s) __builtin_popcount(s)
#define bit(s,x) (((s)>>(x))&1)
inline void solve(){
n=read(),m=read();
if(n==5 && m==15){
n=30,m=13;
for(int s=(1<<m)-1;s<1<<n;s+=lb(s),s|=(1<<(m-pnp(s)))-1){
//cout<<s<<endl;
//assert(pnp(s)==m);
int t[32]={0}; t[0]=t[31]=1;
rep(i,1,30)if(bit(s,i-1))t[i]=1;
bool fl=1;
rep(i,0,31)rep(j,i+1,31)if(t[i]&&t[j])fl &= t[i&j] & t[i|j];
if(fl){
rep(i,0,31)if(t[i])printf("%d ",i);
puts("");
return ;
}
}
}
vector<ll>vec(1,0);
ll cnt=0;
per(i,__lg(m)-1,0){
cnt=cnt<<1|1;
vector<ll>tmp;
for(auto x:vec)tmp.pb(x<<1),tmp.pb(x<<1|1);
if((m>>i)&1){
for(auto &x:tmp)x<<=1;
tmp.pb(cnt=cnt<<1|1);
}
vec.swap(tmp);
}
assert(vec.size() == m);
cnt ^= (1ll<<n)-1;
for(auto &x:vec)if(x&1)x^=cnt;
sort(vec.begin(),vec.end());
for(auto x:vec)printf("%lld ",x);
puts("");
}
int main(){
//freopen("data.in","r",stdin);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int T=read();while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
input:
3 3 5 4 8 60 2
output:
0 2 4 6 7 0 2 4 6 9 11 13 15 0 1152921504606846975
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3736kb
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 2 63 0 2 61 63 0 2 4 6 63 0 4 6 57 61 63 0 2 8 10 12 14 63 0 2 4 6 57 59 61 63 0 2 4 6 8 10 12 14 63 0 4 8 12 14 49 53 57 61 63 0 2 8 10 16 18 24 26 28 30 63 0 2 8 10 12 14 49 51 57 59 61 63 0 2 4 6 16 18 20 22 24 26 28 30 63 0 4 16 20 24 28 30 33 37 49 53 57 61 63 0 2 8 10 32 34...
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3732kb
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 2 8 10 12 14 113 115 121 123 125 127 0 2 4 6 16 18 20 22 24 26 28 30 127 0 4 16 20 24 28 30 97 101 113 117 121 125 127 0 2 8 10 32 34 40 42 48 50 56 58 60 62 127 0 2 4 6 8 10 12 14 113 115 117 119 121 123 125 127 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 127 0 4 8 12 16 20 24 28 30 97 101 1...
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 4016kb
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 2 8 10 32 34 40 42 48 50 56 58 60 62 255 0 2 4 6 8 10 12 14 241 243 245 247 249 251 253 255 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 255 0 4 8 12 16 20 24 28 30 225 229 233 237 241 245 249 253 255 0 2 8 10 16 18 24 26 32 34 40 42 48 50 56 58 60 62 255 0 2 8 10 16 18 24 26 28 30 225 227 233 ...
result:
ok AC
Test #5:
score: 0
Accepted
time: 0ms
memory: 4016kb
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 4 8 12 14 497 501 505 509 511 0 2 8 10 16 18 24 26 28 30 511 0 2 8 10 12 14 497 499 505 507 509 511 0 2 4 6 16 18 20 22 24 26 28 30 511 0 4 16 20 24 28 30 481 485 497 501 505 509 511 0 2 8 10 32 34 40 42 48 50 56 58 60 62 511 0 2 4 6 8 10 12 14 497 499 501 503 505 507 509 511 0 2 4 6 8 10 1...
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
6 9 40 9 41 9 42 9 43 9 44 9 45
output:
0 2 4 6 16 18 20 22 32 34 36 38 48 50 52 54 56 58 60 62 449 451 453 455 465 467 469 471 481 483 485 487 497 499 501 503 505 507 509 511 0 2 4 6 8 10 12 14 32 34 36 38 40 42 44 46 64 66 68 70 72 74 76 78 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 511 0 4 8 12 32 36 40 44 64 68 72...
result:
ok AC
Test #7:
score: 0
Accepted
time: 4ms
memory: 3776kb
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 2 4 6 8 10 12 14 32 34 36 38 40 42 44 46 64 66 68 70 72 74 76 78 96 98 100 102 104 106 108 110 128 130 132 134 136 138 140 142 160 162 164 166 168 170 172 174 192 194 196 198 200 202 204 206 224 226 228 230 232 234 236 238 256 258 260 262 264 266 268 270 288 290 292 294 296 298 300 302 320 322 324...
result:
ok AC
Test #8:
score: 0
Accepted
time: 4ms
memory: 4136kb
input:
30 59 1741 59 1742 59 1743 59 1744 59 1745 59 1746 59 1747 59 1748 59 1749 59 1750 59 1751 59 1752 59 1753 59 1754 59 1755 59 1756 59 1757 59 1758 59 1759 59 1760 59 1761 59 1762 59 1763 59 1764 59 1765 59 1766 59 1767 59 1768 59 1769 59 1770
output:
0 2 4 6 16 18 20 22 64 66 68 70 80 82 84 86 128 130 132 134 144 146 148 150 192 194 196 198 208 210 212 214 256 258 260 262 272 274 276 278 320 322 324 326 336 338 340 342 384 386 388 390 400 402 404 406 448 450 452 454 464 466 468 470 1024 1026 1028 1030 1040 1042 1044 1046 1088 1090 1092 1094 1104...
result:
ok AC
Test #9:
score: 0
Accepted
time: 4ms
memory: 4132kb
input:
30 58 1682 58 1683 58 1684 58 1685 58 1686 58 1687 58 1688 58 1689 58 1690 58 1691 58 1692 58 1693 58 1694 58 1695 58 1696 58 1697 58 1698 58 1699 58 1700 58 1701 58 1702 58 1703 58 1704 58 1705 58 1706 58 1707 58 1708 58 1709 58 1710 58 1711
output:
0 4 8 12 16 20 24 28 64 68 72 76 80 84 88 92 128 132 136 140 144 148 152 156 192 196 200 204 208 212 216 220 256 260 264 268 272 276 280 284 320 324 328 332 336 340 344 348 384 388 392 396 400 404 408 412 448 452 456 460 464 468 472 476 1024 1028 1032 1036 1040 1044 1048 1052 1088 1092 1096 1100 110...
result:
ok AC
Test #10:
score: 0
Accepted
time: 280ms
memory: 3732kb
input:
30 2 2 2 3 3 2 3 3 3 4 3 5 3 6 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 5 14 5 15
output:
0 3 0 2 3 0 7 0 2 7 0 2 5 7 0 2 4 6 7 0 1 4 5 6 7 0 15 0 2 15 0 2 13 15 0 2 4 6 15 0 4 6 9 13 15 0 2 8 10 12 14 15 0 2 4 6 9 11 13 15 0 2 4 6 8 10 12 14 15 0 1 4 5 8 9 12 13 14 15 0 31 0 2 31 0 2 29 31 0 2 4 6 31 0 4 6 25 29 31 0 2 8 10 12 14 31 0 2 4 6 25 27 29 31 0 2 4 6 8 1...
result:
ok AC
Test #11:
score: 0
Accepted
time: 562ms
memory: 3788kb
input:
30 2 3 5 4 4 9 5 4 2 2 5 11 2 2 5 15 3 5 2 3 5 15 2 2 5 9 4 7 4 2 3 5 4 6 2 3 2 2 5 13 5 11 5 9 4 5 4 9 4 6 3 3 5 4 3 5 4 3 4 6
output:
0 2 3 0 2 29 31 0 2 4 6 8 10 12 14 15 0 2 29 31 0 3 0 2 8 10 16 18 24 26 28 30 31 0 3 0 1 2 3 4 5 6 7 12 13 14 15 19 23 31 0 2 4 6 7 0 2 3 0 1 2 3 4 5 6 7 12 13 14 15 19 23 31 0 3 0 2 4 6 8 10 12 14 31 0 2 8 10 12 14 15 0 15 0 2 4 6 7 0 4 6 9 13 15 0 2 3 0 3 0 2 4 6 16 18 20 22 24...
result:
ok AC
Test #12:
score: -100
Time Limit Exceeded
input:
30 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15 5 15