Submission #856443

#	Time	Username	Problem	Language	Result	Execution time	Memory
856443		Tenis0206	Present (RMI21_present)	C++11	29 / 100	3515 ms	428 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int vmax = 40;
const int bsize = 1e6;

long long prec[] = {0, 33751120, 75992704, 116437760, 170614864, 230739856, 290855208, 354085568, 432244832, 531108448, 568870688, 612293120, 651920640, 705855104, 765146688, 826166528};

struct sir
{
    vector<int> st;
    bool fr[vmax + 5];
    int Max;
    sir()
    {
        Max = 0;
        memset(fr,false,sizeof(fr));
    }
};

sir get_next(sir s)
{
    for(int val=1;val<=s.Max+1;val++)
    {
        if((s.st.empty() || s.st.back()!=val) && !s.fr[val])
        {
            s.st.push_back(val);
            break;
        }
        if(!s.st.empty() && s.st.back()==val)
        {
            s.st.pop_back();
        }
    }
    sir rez;
    rez.st = s.st;
    if(rez.st.size())
    {
        rez.Max = rez.st.front();
    }
    for(auto it : rez.st)
    {
        rez.fr[it] = true;
    }
    for(int a=rez.Max;a>=1;a--)
    {
        for(int b=a-1;b>=1;b--)
        {
            if(!rez.fr[a] || !rez.fr[b])
            {
                continue;
            }
            rez.fr[__gcd(a,b)] = true;
        }
    }
    return rez;
}

sir conv_mask(long long val)
{
    sir rez;
    int k = 0;
    for(int b=vmax;b>=1;b--)
    {
        if((val & (1LL<<b)) != 0)
        {
            if(!rez.Max)
            {
                rez.Max = b;
            }
            rez.st.push_back(b);
        }
    }
    for(int a=vmax;a>=1;a--)
    {
        for(int b=a-1;b>=1;b--)
        {
            if(!(val & (1LL<<a)) || !(val & (1LL<<b)) )
            {
                continue;
            }
            val |= (1LL<<__gcd(a,b));
        }
    }
    for(int b=1;b<=vmax;b++)
    {
        if((val & (1LL<<b)) != 0)
        {
            rez.fr[b] = true;
        }
    }
    return rez;
}

void solve_test()
{
    int k;
    cin>>k;
    int start = (k / bsize) * bsize;
    sir rez = conv_mask(prec[k / bsize]);
    for(int i=start+1;i<=k;i++)
    {
        rez = get_next(rez);
    }
    vector<int> r;
    for(int val=1;val<=vmax;val++)
    {
        if(rez.fr[val])
        {
            r.push_back(val);
        }
    }
    cout<<r.size()<<' ';
    for(auto it : r)
    {
        cout<<it<<' ';
    }
    cout<<'\n';
}

int main()
{
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    int t;
    cin>>t;
    for(int test=1;test<=t;test++)
    {
        solve_test();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'sir conv_mask(long long int)':
Main.cpp:63:9: warning: unused variable 'k' [-Wunused-variable]
   63 |     int k = 0;
      |         ^

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 0 / 41
• Subtask 4: 0 / 14
• Subtask 5: 0 / 16