Submission #498646

#	Time	Username	Problem	Language	Result	Execution time	Memory
498646		model_code	Present (RMI21_present)	C++17	100 / 100	763 ms	352 KiB

Main

// 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 / 8
• Subtask 2: 21 / 21
• Subtask 3: 41 / 41
• Subtask 4: 14 / 14
• Subtask 5: 16 / 16