oj.uz

Submission #498646

# Submission time Handle Problem Language Result Execution time Memory
498646 2021-12-26T04:42:44 Z model_code Present (RMI21_present) C++17
100 / 100
 763 ms 352 KB 
// present_100_panaete.cpp
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int,int,int>> GCD;
unordered_map<int64_t,int64_t> D,X;
const int N = 153;
int64_t pre[N]={2,568870846,1233666430,2272958142,2860812970,3802412270,4703718326,5531670398,6711354582,7479904094,8760789726,9744054878,11110679294,12295699198,13593226622,15242871390,16710233790,17639550974,18284289534,19399050174,19987061886,20900760318,21825864446,22658409534,23862816510,24655073278,25950304830,26988500990,28387309310,29628945918,30921016190,32598559742,34234159870,35455318390,37111359990,38816918426,40822902270,42565335038,44848926462,47247085038,49873373918,52086073006,53768459710,55172541678,56896890814,58821341118,60971738046,63316175806,66215685870,68829854838,70066200054,71504939966,73217673782,74964996062,76322683358,78400697310,80610426846,83385876222,85971299774,87104405374,88665051102,90378354622,92154024926,93596778366,95728877166,98075770846,100955404766,103453286334,106048976830,109564372414,112835247998,117378187006,121169718710,124372319998,127443025854,131570212798,136205172478,137917329342,138535644382,139647847214,140221918654,141025607166,142016133598,142810317790,144028280798,144766493790,146096260574,146986775166,148397897598,149418940158,150896644030,152540827614,153763759070,154959867774,155587231486,156772087006,157362815470,158109141230,159151333246,159938445182,161192234878,161943406814,163278178270,164226587582,165641415614,166785007102,168185196478,169856153470,171339956094,172650210814,174367220990,176102580278,177818776958,179560983486,181773034494,184163216638,186965863870,189292046078,190969789950,192267077886,194054680238,196055998334,198176483070,200438066622,203038403518,206170171678,207178973054,208848251102,210489465086,211936978942,213491679166,215558160254,217738247678,220170198526,223138479870,224282287998,225996367614,227661610942,229176786814,230700787582,232806731646,235049123582,237802421246,240598927550,243233223678,246229040638,249739967998,254049206142,258313214462,261059869694,264519794430,268519382206,273108082430};
void precalc(),constantVector(),printInt(int64_t);
struct gcdSet
{
    vector<int64_t> ST;int64_t val;int ord;
    gcdSet(){val=1LL<<1;ST=vector<int64_t>(1,val);ord=1;}
    void nxt(){int64_t aux=val+2LL;int64_t bit=aux&(-aux);while(ST.size()&&ST.back()<bit){val-=ST.back();ST.pop_back();}int64_t di=D[bit]-(D[bit]&val);int64_t st=bit;for(; di;){int64_t diBit=di&(-di);if(X[bit|diBit]&val)st|=diBit;di-=diBit;}ST.push_back(st);val|=st;ord++;}
    void print(){int64_t x=val;cout<<__builtin_popcountll(x)<<' ';while(x){cout<<__builtin_ctzll(x)<<' ';x-=x&(-x);}cout<<'\n';}
};
gcdSet gSet(int);
vector<int64_t> v;
int main()
{
    precalc();
    ///constantVector();
    int t;
    cin>>t;
    for(;t;t--){int k,st=0,dr=N;cin>>k;while(dr-st>1){int mi=(st+dr)/2;if(k>=10000000*mi+1)st=mi;else dr=mi;}gcdSet S=gSet(st);while(S.ord<k)S.nxt();S.print();}
    return 0;
}
void precalc(){for(int i=1; i<=37; i++)for(int j=1; j<=37; j++)GCD.push_back(make_tuple(i,j,__gcd(i,j)));for(auto it:GCD){int i,j,k;tie(i,j,k)=it;int64_t I=1LL<<i,J=1LL<<j,K=1LL<<k;if(i>j){if(K==J){D[I]|=K;}else{X[I|K]|=J;X[J|K]|=I;}}}}
gcdSet gSet(int i){gcdSet ret;int64_t aux=pre[i];vector<int64_t> St;int64_t Val=0LL;int Ord=10000000*i+1;for(int64_t bit=1LL<<37; bit>1LL; bit>>=1)if(aux&bit){int64_t st=bit;int64_t di=D[bit]-(D[bit]&Val);for(; di;){int64_t diBit=di&(-di);if(X[bit|diBit]&Val)st|=diBit;di-=diBit;}St.push_back(st);Val|=st;aux^=st;}ret.val=Val;ret.ST=St;ret.ord=Ord;return ret;}
void constantVector(){gcdSet x;do{x.nxt();}while(x.val<(1LL<<38));}
void printInt(int64_t x){cout<<__builtin_popcountll(x)<<' ';while(x){cout<<__builtin_ctzll(x)<<' ';x-=x&(-x);}cout<<'\n';}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 45 ms 332 KB Output is correct
8 Correct 66 ms 332 KB Output is correct
9 Correct 54 ms 332 KB Output is correct
10 Correct 61 ms 332 KB Output is correct
11 Correct 32 ms 332 KB Output is correct
12 Correct 62 ms 332 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 45 ms 332 KB Output is correct
8 Correct 66 ms 332 KB Output is correct
9 Correct 54 ms 332 KB Output is correct
10 Correct 61 ms 332 KB Output is correct
11 Correct 32 ms 332 KB Output is correct
12 Correct 62 ms 332 KB Output is correct
13 Correct 659 ms 312 KB Output is correct
14 Correct 277 ms 332 KB Output is correct
15 Correct 438 ms 332 KB Output is correct
16 Correct 763 ms 332 KB Output is correct
17 Correct 645 ms 204 KB Output is correct
18 Correct 674 ms 332 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 45 ms 332 KB Output is correct
8 Correct 66 ms 332 KB Output is correct
9 Correct 54 ms 332 KB Output is correct
10 Correct 61 ms 332 KB Output is correct
11 Correct 32 ms 332 KB Output is correct
12 Correct 62 ms 332 KB Output is correct
13 Correct 659 ms 312 KB Output is correct
14 Correct 277 ms 332 KB Output is correct
15 Correct 438 ms 332 KB Output is correct
16 Correct 763 ms 332 KB Output is correct
17 Correct 645 ms 204 KB Output is correct
18 Correct 674 ms 332 KB Output is correct
19 Correct 559 ms 312 KB Output is correct
20 Correct 540 ms 332 KB Output is correct
21 Correct 554 ms 204 KB Output is correct
22 Correct 329 ms 332 KB Output is correct
23 Correct 477 ms 332 KB Output is correct
24 Correct 341 ms 204 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 45 ms 332 KB Output is correct
8 Correct 66 ms 332 KB Output is correct
9 Correct 54 ms 332 KB Output is correct
10 Correct 61 ms 332 KB Output is correct
11 Correct 32 ms 332 KB Output is correct
12 Correct 62 ms 332 KB Output is correct
13 Correct 659 ms 312 KB Output is correct
14 Correct 277 ms 332 KB Output is correct
15 Correct 438 ms 332 KB Output is correct
16 Correct 763 ms 332 KB Output is correct
17 Correct 645 ms 204 KB Output is correct
18 Correct 674 ms 332 KB Output is correct
19 Correct 559 ms 312 KB Output is correct
20 Correct 540 ms 332 KB Output is correct
21 Correct 554 ms 204 KB Output is correct
22 Correct 329 ms 332 KB Output is correct
23 Correct 477 ms 332 KB Output is correct
24 Correct 341 ms 204 KB Output is correct
25 Correct 721 ms 332 KB Output is correct
26 Correct 543 ms 336 KB Output is correct
27 Correct 667 ms 352 KB Output is correct
28 Correct 554 ms 312 KB Output is correct
29 Correct 624 ms 332 KB Output is correct
30 Correct 543 ms 332 KB Output is correct