oj.uz

Submission #856490

# Submission time Handle Problem Language Result Execution time Memory
856490 2023-10-03T16:51:42 Z Tenis0206 Present (RMI21_present) C++11
100 / 100
 2052 ms 5716 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1845 ms 5564 KB Output is correct
2 Correct 1968 ms 5584 KB Output is correct
3 Correct 1873 ms 5564 KB Output is correct
4 Correct 1919 ms 5564 KB Output is correct
5 Correct 1863 ms 5564 KB Output is correct
6 Correct 1900 ms 5568 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1845 ms 5564 KB Output is correct
2 Correct 1968 ms 5584 KB Output is correct
3 Correct 1873 ms 5564 KB Output is correct
4 Correct 1919 ms 5564 KB Output is correct
5 Correct 1863 ms 5564 KB Output is correct
6 Correct 1900 ms 5568 KB Output is correct
7 Correct 1884 ms 5568 KB Output is correct
8 Correct 2011 ms 5568 KB Output is correct
9 Correct 1988 ms 5564 KB Output is correct
10 Correct 1900 ms 5712 KB Output is correct
11 Correct 1899 ms 5576 KB Output is correct
12 Correct 1950 ms 5572 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1845 ms 5564 KB Output is correct
2 Correct 1968 ms 5584 KB Output is correct
3 Correct 1873 ms 5564 KB Output is correct
4 Correct 1919 ms 5564 KB Output is correct
5 Correct 1863 ms 5564 KB Output is correct
6 Correct 1900 ms 5568 KB Output is correct
7 Correct 1884 ms 5568 KB Output is correct
8 Correct 2011 ms 5568 KB Output is correct
9 Correct 1988 ms 5564 KB Output is correct
10 Correct 1900 ms 5712 KB Output is correct
11 Correct 1899 ms 5576 KB Output is correct
12 Correct 1950 ms 5572 KB Output is correct
13 Correct 1894 ms 5568 KB Output is correct
14 Correct 1903 ms 5568 KB Output is correct
15 Correct 1876 ms 5564 KB Output is correct
16 Correct 1927 ms 5568 KB Output is correct
17 Correct 2052 ms 5568 KB Output is correct
18 Correct 1991 ms 5716 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1845 ms 5564 KB Output is correct
2 Correct 1968 ms 5584 KB Output is correct
3 Correct 1873 ms 5564 KB Output is correct
4 Correct 1919 ms 5564 KB Output is correct
5 Correct 1863 ms 5564 KB Output is correct
6 Correct 1900 ms 5568 KB Output is correct
7 Correct 1884 ms 5568 KB Output is correct
8 Correct 2011 ms 5568 KB Output is correct
9 Correct 1988 ms 5564 KB Output is correct
10 Correct 1900 ms 5712 KB Output is correct
11 Correct 1899 ms 5576 KB Output is correct
12 Correct 1950 ms 5572 KB Output is correct
13 Correct 1894 ms 5568 KB Output is correct
14 Correct 1903 ms 5568 KB Output is correct
15 Correct 1876 ms 5564 KB Output is correct
16 Correct 1927 ms 5568 KB Output is correct
17 Correct 2052 ms 5568 KB Output is correct
18 Correct 1991 ms 5716 KB Output is correct
19 Correct 1840 ms 5568 KB Output is correct
20 Correct 1920 ms 5568 KB Output is correct
21 Correct 1848 ms 5572 KB Output is correct
22 Correct 1984 ms 5572 KB Output is correct
23 Correct 1864 ms 5568 KB Output is correct
24 Correct 1971 ms 5564 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1845 ms 5564 KB Output is correct
2 Correct 1968 ms 5584 KB Output is correct
3 Correct 1873 ms 5564 KB Output is correct
4 Correct 1919 ms 5564 KB Output is correct
5 Correct 1863 ms 5564 KB Output is correct
6 Correct 1900 ms 5568 KB Output is correct
7 Correct 1884 ms 5568 KB Output is correct
8 Correct 2011 ms 5568 KB Output is correct
9 Correct 1988 ms 5564 KB Output is correct
10 Correct 1900 ms 5712 KB Output is correct
11 Correct 1899 ms 5576 KB Output is correct
12 Correct 1950 ms 5572 KB Output is correct
13 Correct 1894 ms 5568 KB Output is correct
14 Correct 1903 ms 5568 KB Output is correct
15 Correct 1876 ms 5564 KB Output is correct
16 Correct 1927 ms 5568 KB Output is correct
17 Correct 2052 ms 5568 KB Output is correct
18 Correct 1991 ms 5716 KB Output is correct
19 Correct 1840 ms 5568 KB Output is correct
20 Correct 1920 ms 5568 KB Output is correct
21 Correct 1848 ms 5572 KB Output is correct
22 Correct 1984 ms 5572 KB Output is correct
23 Correct 1864 ms 5568 KB Output is correct
24 Correct 1971 ms 5564 KB Output is correct
25 Correct 1945 ms 5460 KB Output is correct
26 Correct 1933 ms 5564 KB Output is correct
27 Correct 1943 ms 5568 KB Output is correct
28 Correct 1941 ms 5568 KB Output is correct
29 Correct 1933 ms 5568 KB Output is correct
30 Correct 1902 ms 5568 KB Output is correct