QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422424#8174. Set Construction_qwqUwUTL 562ms4136kbC++201.5kb2024-05-27 14:11:192024-05-27 14:11:19

Judging History

你现在查看的是最新测评结果

  • [2024-05-27 14:11:19]
  • 评测
  • 测评结果:TL
  • 用时:562ms
  • 内存:4136kb
  • [2024-05-27 14:11:19]
  • 提交

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

output:


result: