Submission #737108

#	Time	Username	Problem	Language	Result	Execution time	Memory
737108		ibm2006	Present (RMI21_present)	C++14	29 / 100	504 ms	52692 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll l,z,w,n,i,x,y,t,j,a[110000],m,k,b[1100]={0,62615,127831,217175,296639,362015,443455,538687,659719,804895,925799,1075695,1196111,1345741,1467607,1646511,1901295,2111107,2189639,2275563,2372147,2449895,2537011,2640287,2777503,2929323,3080739,3223911,3393495,3532759,3730271,3999527,4209167,4274335,4351199,4449503,4516479,4581311,4671423,4784319,4916863,5048543,5183231,5313167,5456287,5580287,5729391,5935295,6168447,6336095,6415551,6512863,6597055,6676703,6772543,6890079,7042303,7179359,7341663,7477503,7643727,7803039,8028607,8296831,8456703,8593903,8720935,8861679,9087147,9349823,9564415,9785687,10110463,10503935,10632383,10806271,10957951,11217023,11512063,11769855,12028927,12519679,12660895,12827647,12925823,13108479,13370783,13632655,13830015,14025727,14427903,14725567,14882879,15019103,15208319,15478847,15752191,16013183,16319359,16783671,16875563};
vector<ll> v,u[1100000],q;
ll gcd(ll x,ll y)
{
    if(x>y)
        x^=y^=x^=y;
    if(y%x==0)
        return x;
    return gcd(y%x,x);
}
int main()
{
    scanf("%lld",&n);
    for(l=0;l<n;l++)
    {
        scanf("%lld",&z);
        w=b[z/10000];
        t=z/10000*10000;

        for(i=w;1;i++)
    {

            v.clear();
            q.clear();
        x=i; y=0;
        while(x>0)
        {
            v.push_back(x%2);
            if(x%2==1)
                q.push_back(y+1);
            x/=2;
            y++;

        }
        for(j=y-1;j>=0;j--)
            {a[j+1]=v[j];  /*printf("%lld:%lld ",j+1,a[j+1]);*/  }
        if(i==0)
        {
            u[t]=q;
            t++;
            continue;
        }
        for(j=1;j<=y;j++)
            for(k=j+1;k<=y;k++)
        {
            if(a[j]==0||a[k]==0)
                continue;
            if(a[gcd(j,k)]==0)
            {
                x=-1;
               // printf("!");
                break;
            }
        }
        //printf("%lld %lld\n",i,x);
        if(x==0)
        {
            u[t]=q;
            if(t==z)
                break;
            t++;
            continue;
        }
    }
    m=u[z].size();
    printf("%lld ",m);
    for(i=0;i<m;i++)
        printf("%lld ",u[z][i]);
    printf("\n");
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%lld",&z);
      |         ~~~~~^~~~~~~~~~~

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