QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #822165 | #2809. Present | Pure_Furies | 100 ✓ | 2676ms | 60784kb | C++14 | 1.7kb | 2024-12-19 23:03:07 | 2024-12-19 23:03:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int g[43][43],k;
bool ok[524288];
int w[6];
int dp[7][524288],n[7],m[7];
vector<int>v[20];
int cnt=0;
int gen[10][1048576];
bool check(int a,int b){
for(int i=0;i<10;i++)
if((a&1<<i)&&(gen[i][b]|b)!=b)
return 0;
return 1;
}
int query(int t,long long msk){
memset(w,0,sizeof(w));
memset(n,0,sizeof(n));
memset(m,0,sizeof(m));
for(int i=0;i<6;i++)
for(int j=(1<<i);j<=38;j+=(1<<i+1)){
if(msk&1ll<<j)
w[i]|=(1ll<<(j>>i+1));
n[i]++;if(j<=t)m[i]++;
}
for(int i=6;i>0;i--){
memset(dp[i-1],0,(1<<n[i-1]+2));
vector<int>t;
for(auto k:v[n[i-1]])
if((k>>m[i-1])==(w[i-1]>>m[i-1]))
t.push_back(k);
for(auto j:v[n[i]])
if(dp[i][j])
for(auto k:t)
if(ok[j|k]&&(k>>m[i-1])==(w[i-1]>>m[i-1])&&check(j,k))
dp[i-1][j|k]+=dp[i][j];
}
int ret=0;
for(int i=0;i<(1<<19);i++)
ret+=dp[0][i];
return ret;
}
int main(){
dp[6][0]=1;
for(int i=0;i<=19;i++)
for(int j=0;j<=19;j++)
g[i][j]=(__gcd(i<<1|1,j<<1|1)>>1);
ok[0]=1;
for(int i=0;i<19;i++)
for(int j=(1<<i);j<(1<<i+1);j++)
if(ok[j^1<<i]){
ok[j]=1;
for(int k=0;k<i;k++)
if((j&1<<k)&&(~j&1<<g[i][k]))
ok[j]=0;
}
for(int i=0;i<10;i++)
for(int j=0;j<19;j++)
for(int k=(1<<j);k<(1<<j+1);k++)
gen[i][k]=gen[i][k^1<<j]|1<<g[i][j];
for(int i=0;i<=19;i++)
for(int j=0;j<(1<<i);j++)
if(ok[j])
v[i].push_back(j);
int T;
cin>>T;
while(T--){
cin>>k;k++;
long long msk=0;
for(int i=38;i>0;i--){
int t=query(i-1,msk);
if(t<k)
msk|=1ll<<i,k-=t;
}
cout<<__builtin_popcountll(msk)<<' ';
for(int i=1;i<=38;i++)
if(msk&1ll<<i)
cout<<i<<' ';
cout<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 2623ms
memory: 49680kb
input:
5 62 37 88 57 72
output:
5 1 2 5 6 7 6 1 2 3 4 5 6 4 1 2 6 8 4 1 3 6 7 4 1 2 3 8
result:
ok 5 lines
Test #2:
score: 8
Accepted
time: 2620ms
memory: 58416kb
input:
5 88 77 21 87 24
output:
4 1 2 6 8 4 1 3 4 8 5 1 2 3 4 5 3 2 6 8 2 2 6
result:
ok 5 lines
Test #3:
score: 8
Accepted
time: 2614ms
memory: 60096kb
input:
5 59 5 72 76 95
output:
5 1 2 4 6 7 2 1 3 4 1 2 3 8 4 1 2 4 8 6 1 2 4 5 6 8
result:
ok 5 lines
Test #4:
score: 8
Accepted
time: 2676ms
memory: 44844kb
input:
5 3 58 50 91 38
output:
2 1 2 5 1 2 3 6 7 5 1 2 3 5 7 5 1 2 4 6 8 1 7
result:
ok 5 lines
Test #5:
score: 8
Accepted
time: 2617ms
memory: 49348kb
input:
5 6 38 78 60 52
output:
3 1 2 3 1 7 5 1 2 3 4 8 6 1 2 3 4 6 7 5 1 2 4 5 7
result:
ok 5 lines
Test #6:
score: 8
Accepted
time: 2631ms
memory: 50320kb
input:
5 53 2 54 17 77
output:
5 1 3 4 5 7 1 2 6 1 2 3 4 5 7 4 1 2 3 5 4 1 3 4 8
result:
ok 5 lines
Subtask #2:
score: 21
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 21
Accepted
time: 2629ms
memory: 53488kb
input:
5 967473 149056 95798 903699 54343
output:
14 1 2 3 6 7 9 14 15 17 18 21 22 23 24 7 1 3 4 8 17 20 21 9 1 2 5 7 11 15 17 19 20 17 1 2 3 4 6 7 8 10 12 13 14 18 19 20 21 23 24 7 1 2 4 8 11 18 19
result:
ok 5 lines
Test #8:
score: 21
Accepted
time: 2611ms
memory: 56976kb
input:
5 824612 692511 834141 820975 111302
output:
14 1 2 3 4 5 6 7 9 10 11 12 18 23 24 10 1 2 3 5 6 7 10 13 21 24 11 1 3 7 8 9 11 13 15 19 23 24 11 1 3 4 5 8 9 12 15 17 23 24 10 1 2 3 4 6 11 12 13 16 21
result:
ok 5 lines
Test #9:
score: 21
Accepted
time: 2625ms
memory: 45864kb
input:
5 115600 813100 742542 206782 714068
output:
13 1 2 3 5 6 7 9 10 11 13 15 17 21 9 1 2 3 4 11 12 14 23 24 12 1 2 3 5 6 11 12 14 17 18 22 24 11 1 2 3 5 7 9 11 12 17 19 22 14 1 2 3 4 5 6 9 10 13 17 18 19 21 24
result:
ok 5 lines
Test #10:
score: 21
Accepted
time: 2661ms
memory: 52144kb
input:
5 271953 490598 560137 729339 980828
output:
14 1 2 3 4 6 7 8 9 11 13 16 17 21 22 12 1 2 3 4 8 11 12 13 14 16 22 23 12 1 2 4 6 7 10 16 17 18 20 22 23 12 1 2 3 5 7 8 9 10 13 14 22 24 17 1 2 3 4 5 6 7 10 11 12 15 17 20 21 22 23 24
result:
ok 5 lines
Test #11:
score: 21
Accepted
time: 2628ms
memory: 54148kb
input:
5 78005 94222 345802 240639 797525
output:
14 1 2 3 4 6 7 9 10 11 12 13 16 17 20 12 1 2 3 4 5 6 7 11 13 17 19 20 12 1 2 3 7 8 9 11 13 14 17 18 23 13 1 2 3 4 5 6 7 10 13 16 18 20 22 13 1 2 3 6 7 8 9 14 18 19 21 22 24
result:
ok 5 lines
Test #12:
score: 21
Accepted
time: 2631ms
memory: 56292kb
input:
5 213815 388934 704608 638223 965441
output:
15 1 2 3 4 5 6 9 10 11 13 15 16 17 19 22 11 1 2 3 4 7 10 13 14 16 20 23 14 1 2 3 4 5 6 8 9 10 11 13 19 21 24 8 1 2 4 8 11 14 16 24 17 1 2 3 4 6 7 8 10 11 12 13 14 18 21 22 23 24
result:
ok 5 lines
Subtask #3:
score: 41
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #13:
score: 41
Accepted
time: 2616ms
memory: 45152kb
input:
5 264009813 338082986 193952046 78609665 69397288
output:
21 1 2 3 4 5 6 7 8 9 10 12 15 17 18 19 21 24 25 29 33 34 21 1 2 3 4 5 6 7 8 9 10 12 13 14 15 17 23 24 26 28 31 35 20 1 2 3 4 5 7 10 11 13 14 15 16 17 20 21 22 23 28 31 34 17 1 2 3 4 7 8 9 14 16 17 19 20 21 24 27 31 32 18 1 2 3 4 5 6 7 8 10 13 15 17 18 19 24 26 30 32
result:
ok 5 lines
Test #14:
score: 41
Accepted
time: 2541ms
memory: 58048kb
input:
5 150219445 322427094 31308257 148721382 412214364
output:
16 1 2 3 4 9 11 13 14 17 18 25 26 27 31 32 33 16 1 2 3 4 5 7 9 10 11 12 17 21 23 24 27 35 15 1 2 3 5 8 9 11 13 15 16 17 18 26 27 31 19 1 2 3 5 8 9 10 11 13 16 17 18 21 22 23 26 31 32 33 17 1 2 3 4 5 7 9 13 18 20 21 22 26 27 29 34 35
result:
ok 5 lines
Test #15:
score: 41
Accepted
time: 2525ms
memory: 57296kb
input:
5 151756875 427011464 58969849 244330943 310625967
output:
21 1 2 3 4 5 6 7 8 9 10 11 18 19 20 23 24 27 28 31 32 33 22 1 2 3 4 5 6 7 8 9 16 17 18 19 20 22 23 26 28 29 31 34 35 15 1 2 4 5 7 8 10 14 16 19 22 24 25 28 32 19 1 2 3 4 5 6 8 10 15 16 17 18 23 24 25 29 31 32 34 25 1 2 3 4 5 6 7 10 11 12 13 14 15 17 20 21 22 23 26 27 28 31 32 33 34
result:
ok 5 lines
Test #16:
score: 41
Accepted
time: 2499ms
memory: 43872kb
input:
5 179476159 129836662 494167066 336058841 348325607
output:
22 1 2 3 4 5 6 7 8 12 13 15 16 19 21 23 24 25 26 27 28 29 34 22 1 2 3 4 5 6 8 9 10 11 13 14 17 18 20 22 25 27 28 30 31 33 17 1 2 3 4 5 6 7 9 10 14 16 18 19 22 25 29 36 22 1 2 3 4 5 7 8 9 10 11 12 13 14 15 19 20 23 24 25 26 31 35 22 1 2 3 4 5 6 7 10 11 15 19 22 23 24 25 26 27 28 29 30 31 35
result:
ok 5 lines
Test #17:
score: 41
Accepted
time: 2401ms
memory: 52056kb
input:
5 337931259 398093956 349469813 381304523 455533754
output:
15 1 2 3 5 6 7 9 13 15 21 22 26 28 31 35 17 1 2 3 4 5 7 9 11 15 17 19 21 26 31 32 33 35 18 1 2 3 4 5 7 8 10 11 12 14 15 16 21 25 26 32 35 17 1 2 3 4 5 10 11 13 15 17 20 22 24 26 31 33 35 22 1 2 3 4 5 6 7 8 9 10 13 14 16 18 19 20 21 23 26 33 34 35
result:
ok 5 lines
Test #18:
score: 41
Accepted
time: 2564ms
memory: 60116kb
input:
5 5456876 29594798 37782325 167839691 354330184
output:
17 1 2 3 4 5 6 9 12 13 17 20 21 23 24 25 26 27 12 1 2 3 4 5 14 16 18 22 25 26 31 16 1 2 4 5 6 7 10 11 16 17 18 19 22 26 29 31 18 1 2 3 4 5 6 8 9 10 13 14 15 17 20 23 24 28 34 19 1 2 3 4 5 6 8 9 10 16 17 20 23 24 26 27 29 32 35
result:
ok 5 lines
Subtask #4:
score: 14
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #19:
score: 14
Accepted
time: 2172ms
memory: 53852kb
input:
5 518437301 666694742 559265585 512923635 621833328
output:
20 1 2 3 4 5 7 8 9 10 12 13 15 17 19 21 22 23 24 32 36 24 1 2 3 4 5 6 7 8 11 12 13 15 16 19 21 22 25 29 30 31 32 33 34 36 25 1 2 3 4 6 7 8 9 10 11 12 13 14 16 19 20 22 23 24 27 28 29 31 33 36 15 1 2 4 5 7 9 11 14 18 20 27 28 29 31 36 21 1 2 3 4 5 6 8 9 11 12 16 19 20 21 22 25 26 31 32 34 36
result:
ok 5 lines
Test #20:
score: 14
Accepted
time: 2380ms
memory: 44304kb
input:
5 633963943 615542568 828135456 568557686 770592955
output:
17 1 2 3 4 7 8 9 11 12 13 14 24 25 26 33 34 36 16 1 2 3 4 6 7 10 13 17 20 26 28 29 32 34 36 18 1 2 4 6 7 11 13 14 16 17 19 20 23 26 28 29 32 37 18 1 2 3 4 5 6 7 11 12 16 17 21 22 26 30 32 33 36 11 1 2 3 4 5 9 10 13 19 29 37
result:
ok 5 lines
Test #21:
score: 14
Accepted
time: 2505ms
memory: 58228kb
input:
5 872589670 817203941 677799344 886039387 913475137
output:
20 1 2 3 4 5 6 8 11 12 15 16 17 19 23 25 26 27 30 33 37 19 1 2 3 4 5 6 7 8 10 12 13 15 16 18 22 24 26 32 37 23 1 2 3 4 5 6 7 9 10 12 13 14 16 19 21 22 23 25 26 28 31 35 36 20 1 2 3 4 5 6 8 10 11 17 19 22 23 24 26 27 29 31 33 37 27 1 2 3 4 5 6 7 8 10 11 12 13 14 16 19 20 21 22 23 24 25 27 28 31 3...
result:
ok 5 lines
Test #22:
score: 14
Accepted
time: 2432ms
memory: 43012kb
input:
5 670654397 910193787 921254051 975272734 607399529
output:
18 1 2 3 5 6 7 10 11 12 13 14 18 19 21 23 29 35 36 20 1 2 3 4 5 6 7 9 10 12 13 19 20 21 23 26 31 32 33 37 27 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 23 29 30 31 32 33 37 17 1 2 3 5 6 9 14 22 23 25 26 28 29 30 31 34 37 18 1 2 4 5 6 7 10 11 16 22 23 25 28 29 30 31 34 36
result:
ok 5 lines
Test #23:
score: 14
Accepted
time: 2329ms
memory: 60784kb
input:
5 628012728 924251460 522922329 904744468 644444189
output:
20 1 2 3 4 6 8 12 14 16 17 19 20 22 26 28 29 31 32 34 36 18 1 2 4 6 7 8 10 12 14 16 17 18 19 20 22 24 34 37 19 1 2 3 4 6 7 8 9 10 12 14 17 18 22 23 24 29 32 36 15 1 2 3 4 6 11 12 17 21 22 26 30 32 33 37 22 1 2 3 4 5 6 8 10 11 12 14 15 16 18 19 20 25 28 31 33 34 36
result:
ok 5 lines
Test #24:
score: 14
Accepted
time: 2605ms
memory: 48584kb
input:
5 980123780 914372233 788153300 820127076 873721786
output:
19 1 2 3 5 7 10 11 13 14 16 17 21 23 25 26 27 32 34 37 24 1 2 3 4 5 6 7 8 10 11 15 17 18 19 20 21 22 23 24 29 31 32 33 37 20 1 2 3 4 6 9 11 12 13 14 15 17 19 23 26 27 28 29 30 37 11 1 4 5 8 11 16 23 24 28 32 37 21 1 2 3 4 5 6 7 9 10 12 13 14 15 21 25 26 27 28 30 33 37
result:
ok 5 lines
Subtask #5:
score: 16
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #25:
score: 16
Accepted
time: 2231ms
memory: 45908kb
input:
5 1358094333 1154803687 1277000267 1417906383 1326768836
output:
18 1 2 3 4 7 8 13 14 16 17 19 20 23 28 31 34 36 37 20 1 2 3 4 5 8 10 11 13 16 17 20 23 25 26 29 32 33 35 37 26 1 2 3 4 5 6 7 8 9 10 11 12 16 17 19 21 22 23 24 25 26 28 30 31 36 37 22 1 2 3 4 5 6 7 8 10 13 15 20 21 23 25 28 29 32 33 34 36 37 17 1 2 3 4 5 9 15 18 20 23 26 27 28 32 33 36 37
result:
ok 5 lines
Test #26:
score: 16
Accepted
time: 2301ms
memory: 45520kb
input:
5 1100135829 1287342975 1408078880 1246372296 1263782767
output:
21 1 2 3 4 5 6 7 11 12 13 14 15 16 21 23 25 27 28 31 35 37 22 1 2 3 4 5 6 7 9 10 11 14 18 19 20 21 23 26 28 29 32 36 37 21 1 2 3 4 5 8 10 11 13 15 16 18 21 25 26 29 31 33 34 36 37 24 1 2 3 4 5 6 7 10 12 14 15 16 18 19 23 25 28 29 31 32 33 34 35 37 21 1 2 3 4 5 6 7 8 9 11 12 13 15 16 18 24 28 29 ...
result:
ok 5 lines
Test #27:
score: 16
Accepted
time: 2171ms
memory: 57440kb
input:
5 1306529540 1338402393 1435825745 1298031139 1263046790
output:
9 1 3 4 13 19 28 33 36 37 22 1 2 3 4 5 6 7 9 10 11 13 14 19 20 21 27 30 31 32 33 36 37 24 1 2 3 4 5 6 7 8 9 10 12 13 14 16 19 24 25 26 27 28 30 35 36 37 22 1 2 3 4 5 6 7 9 11 12 13 14 16 22 23 25 26 29 31 32 36 37 21 1 2 4 5 6 7 8 10 11 12 14 16 19 20 22 24 26 29 30 36 37
result:
ok 5 lines
Test #28:
score: 16
Accepted
time: 2237ms
memory: 53264kb
input:
5 1299841326 1050490081 1319190964 1496700273 1351264279
output:
19 1 2 3 4 6 8 9 13 15 18 19 23 26 28 29 31 32 36 37 22 1 2 3 4 5 6 7 9 10 12 14 17 21 23 26 27 28 30 31 33 34 37 20 1 3 4 5 7 8 9 12 16 17 19 20 23 24 27 29 31 33 36 37 27 1 2 3 4 5 6 7 8 9 10 12 13 15 16 17 18 20 21 22 25 27 30 32 34 35 36 37 24 1 2 3 4 5 6 7 8 10 12 13 14 16 17 18 20 21 22 23...
result:
ok 5 lines
Test #29:
score: 16
Accepted
time: 2388ms
memory: 57800kb
input:
5 1126333587 1363542178 1219832547 1117001699 1052017949
output:
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 17 18 19 22 23 25 26 29 31 32 35 37 18 1 2 4 5 11 13 14 16 17 19 22 25 28 29 31 34 36 37 23 1 2 3 4 5 6 7 8 9 11 14 16 17 18 19 22 23 25 29 33 34 35 37 21 1 2 3 4 5 6 7 8 9 11 15 16 19 20 23 27 28 29 32 35 37 20 1 2 3 4 5 8 9 10 11 13 21 23 25 27 29 30 31 33 3...
result:
ok 5 lines
Test #30:
score: 16
Accepted
time: 2333ms
memory: 56336kb
input:
5 1419871457 1342818229 1195637683 1225498668 1123546639
output:
22 1 2 3 4 5 6 9 11 13 14 15 16 19 23 27 28 30 32 33 34 36 37 15 1 2 3 4 5 6 8 9 13 16 26 27 34 36 37 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 18 19 20 22 24 27 32 34 35 37 23 1 2 3 4 5 7 10 13 14 15 16 20 23 25 26 27 28 29 30 33 34 35 37 23 1 2 3 4 5 6 7 8 10 11 13 15 16 17 21 24 25 26 27 31 32 35 37
result:
ok 5 lines