QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #785707 | #2809. Present | snpmrnhlol | 8 | 2658ms | 3780kb | C++17 | 1.1kb | 2024-11-26 18:52:40 | 2024-11-26 18:52:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 40;
//const int step = 1e6;
ll x;
int gcdd[N + 1][N + 1];
void make_gcd_closed(ll& x){
for(int i = N;i >= 1;i--){
for(int j = N;j >= 1;j--){
if((x>>i&1) && (x>>j&1)){
x|=(1ll<<gcdd[i][j]);
}
}
}
}
void get_next_set(ll& x){
for(int i = 1;i <= N;i++){
if(!(x>>i&1)){
x|=(1ll<<i);
break;
}
x^=(1ll<<i);
}
make_gcd_closed(x);
}
void dbg(ll x){
for(int i = 1;i <= N;i++){
if(x>>i&1){
cout<<i<<' ';
}
}
cout<<'\n';
}
void solve(){
int x;
cin>>x;
ll nr = 0;
for(int i = 0;i < x;i++){
get_next_set(nr);
}
cout<<__builtin_popcount(nr)<<' ';
dbg(nr);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
for(int i = 1;i <= N;i++){
for(int j = 1;j <= N;j++){
gcdd[i][j] = __gcd(i, j);
}
}
int t;
cin>>t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 1ms
memory: 3608kb
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: 1ms
memory: 3780kb
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: 1ms
memory: 3740kb
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: 1ms
memory: 3524kb
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: 1ms
memory: 3604kb
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: 1ms
memory: 3496kb
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: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #7:
score: 21
Accepted
time: 2658ms
memory: 3484kb
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: 0
Time Limit Exceeded
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:
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%