Submission #856490

#	Time	Username	Problem	Language	Result	Execution time	Memory
856490		Tenis0206	Present (RMI21_present)	C++11	100 / 100	2052 ms	5716 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int n = 19;

int my_gcd[2 * n + 5][2 * n + 5];

bool ok_par[(1<<n) + 5], ok_imp[(1<<n) + 5];

int dp[(1<<n) + 5], mask_c[(1<<n) + 5];

int first_bit(int mask)
{
    for(int b=n-1; b>=0; b--)
    {
        if((mask & (1<<b)) != 0)
        {
            return b;
        }
    }
    return 0;
}

void precalc()
{
    for(int i=1; i<=2*n; i++)
    {
        for(int j=1; j<=2*n; j++)
        {
            my_gcd[i][j] = __gcd(i,j);
        }
    }
    ok_par[0] = 1;
    for(int mask_par=1; mask_par<(1<<n); mask_par++)
    {
        int k = first_bit(mask_par);
        if(!ok_par[mask_par - (1<<k)])
        {
            continue;
        }
        ok_par[mask_par] = true;
        for(int b=0; b<k; b++)
        {
            if((mask_par & (1<<b))==0)
            {
                continue;
            }
            int i = 2 * (k + 1), j = 2 * (b + 1);
            int c = my_gcd[i][j];
            if((mask_par & (1<<(c / 2 - 1))) == 0)
            {
                ok_par[mask_par] = false;
                break;
            }
        }
    }
    ok_imp[0] = 1;
    for(int mask_imp=1; mask_imp<(1<<n); mask_imp++)
    {
        int k = first_bit(mask_imp);
        if(!ok_imp[mask_imp - (1<<k)])
        {
            continue;
        }
        ok_imp[mask_imp] = true;
        for(int b=0; b<k; b++)
        {
            if((mask_imp & (1<<b))==0)
            {
                continue;
            }
            int i = 2 * k + 1, j = 2 * b + 1;
            int c = my_gcd[i][j];
            if((mask_imp & (1<<(c / 2))) == 0)
            {
                ok_imp[mask_imp] = false;
                break;
            }
        }
    }
    for(int mask_imp=0; mask_imp<(1<<n); mask_imp++)
    {
        if(!ok_imp[mask_imp])
        {
            continue;
        }
        for(int k=0; k<n; k++)
        {
            bool ok = true;
            for(int b=0; b<n; b++)
            {
                if((mask_imp & (1<<b)) == 0)
                {
                    continue;
                }
                int i = 2 * k + 1, j = 2 * b + 1;
                int c = my_gcd[i][j];
                if((mask_imp & (1<<(c / 2))) == 0)
                {
                    ok = false;
                }
            }
            if(ok)
            {
                mask_c[mask_imp] += (1<<k);
            }
        }
    }
}

long long find_new(int val, int rez_par, int rez_imp)
{
    int poz_par = 0, poz_imp = 0;
    if(val % 2 == 0)
    {
        poz_par = val / 2 - 1;
        poz_imp = val / 2;
    }
    else
    {
        poz_par = val / 2;
        poz_imp = val / 2;
    }

    for(int mask=0;mask<(1<<n);mask++)
    {
        dp[mask] = 0;
    }

    for(int mask_imp=0; mask_imp < (1<<n); mask_imp++)
    {
        if(!ok_imp[mask_imp] || (rez_imp >> poz_imp) != (mask_imp >> poz_imp))
        {
            continue;
        }
        dp[mask_c[mask_imp]] += 1;
    }

    for(int b=0; b<n; b++)
    {
        for(int mask=0; mask<(1<<n); mask++)
        {
            if((mask & (1<<b)) != 0)
            {
                continue;
            }
            dp[mask] += dp[mask + (1<<b)];
        }
    }

    long long rez = 0;
    for(int mask_par=0; mask_par < (1<<n); mask_par++)
    {
        if(!ok_par[mask_par] || (rez_par >> poz_par) != (mask_par >> poz_par))
        {
            continue;
        }
        int mask_comp = 0;
        for(int i=0; i<n; i++)
        {
            if((mask_par & (1<<i)) == 0)
            {
                continue;
            }
            int val = 2 * (i + 1);
            while(val % 2 == 0)
            {
                val /= 2;
            }
            mask_comp |= (1 << (val / 2));
        }
        rez += dp[mask_comp];
    }
    return rez;
}

void solve_test()
{
    long long k;
    cin>>k;
    int poz_par = n - 1, poz_imp = n - 1;
    long long rez_par = 0, rez_imp = 0;
    vector<int> r;
    for(int val=2*n; val>=1; val--)
    {
        long long cur = find_new(val, rez_par, rez_imp);
        if(cur <= k)
        {
            k -= cur;
            if(val % 2 == 0)
            {
                rez_par += (1LL << (val / 2 - 1));
            }
            else
            {
                rez_imp += (1LL << (val / 2));
            }
            r.push_back(val);
        }
    }
    cout<<r.size()<<' ';
    reverse(r.begin(),r.end());
    for(auto it : r)
    {
        cout<<it<<' ';
    }
    cout<<'\n';
}

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

Compilation message (stderr)

Main.cpp: In function 'void solve_test()':
Main.cpp:182:9: warning: unused variable 'poz_par' [-Wunused-variable]
  182 |     int poz_par = n - 1, poz_imp = n - 1;
      |         ^~~~~~~
Main.cpp:182:26: warning: unused variable 'poz_imp' [-Wunused-variable]
  182 |     int poz_par = n - 1, poz_imp = n - 1;
      |                          ^~~~~~~

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