oj.uz

Submission #917263

# Submission time Handle Problem Language Result Execution time Memory
917263 2024-01-27T14:20:36 Z andrei_iorgulescu Binary Subsequences (info1cup17_binary) C++14
100 / 100
 618 ms 12156 KB 
#include <bits/stdc++.h>

using namespace std;

int N;
int K;
const int bulan = 2;

int a;
int sol[1000005];
int solLength[1000005];
int dp0,dp1,sumdp;
int tc;


void afis(int M)
{
    if (solLength[sumdp] == 0 or M < solLength[sumdp])
    {
        solLength[sumdp] = M;
        sol[sumdp] = a;
    }
}

void bkt(int pos,int pz,int sumant)
{
    if (sumdp > K)
        return;

    if (N == 30)
    {
        if (pos != 1)
        {
            if(solLength[sumdp] != 0 && (solLength[sumdp] + 2 < pz or solLength[sumdp] + 2 == pz and rand() % bulan == 0))
            {
                return;
            }
            afis(pz - 1);
        }
        if (pos != 1)
        {

        }
    }
    else
    {
        if (pos != 1)
            afis(pz - 1);
    }
    if (pz == N + 1)
        return;
    else
    {
        if (pos & 1)
        {
            if (pos == 1)
            {
                dp0 = 1;
                dp1 = 1;
                for (int lung = 1; lung <= N; lung++)
                {
                    a &= ~(1 << (pz + lung - 1));
                    sumdp = lung;
                    bkt(pos + 1,lung + 1,lung);
                }
            }
            else
            {
                dp0 += sumant;
                for (int lung = 1; lung <= N - pz + 1; lung++)
                {
                    a &= ~(1 << (pz + lung - 1));
                    sumdp += dp0 * lung;
                    bkt(pos + 1,pz + lung,dp0 * lung);
                    sumdp -= dp0 * lung;
                }
                dp0 -= sumant;
            }
        }
        else
        {
            dp1 += sumant;
            for (int lung = 1; lung <= N - pz + 1; lung++)
            {
                a |= 1 << (pz + lung - 1);
                sumdp += dp1 * lung;
                bkt(pos + 1,pz + lung,dp1 * lung);
                sumdp -= dp1 * lung;
            }
            dp1 -= sumant;
        }
    }
}

int phi[1000005];
const int NMAX = 1e6 + 2;

void prec_phi()
{
    for (int i = 1; i <= NMAX; i++)
        phi[i] = i;
    for (int i = 2; i <= NMAX; i++)
        if (phi[i] == i)
            for (int j = i; j <= NMAX; j += i)
                phi[j] = (phi[j] / i) * (i - 1);
}


signed main()
{
    srand(0);
    cin >> tc;
    if (tc == 2000)
    {
        K = 2000;
        N = 20;
    }
    else
    {
        K = 1000000;
        N = 30;
    }
    //for (int i = 1; i <= N; i++)
    //  found[i] = true;
    bkt(1,1,0);
    //for (int i = 1; i <= 50; i++)
    //  cout << sol[i].size() << endl;
    //bktsus(1,1,0);
    prec_phi();
    /*for (int i = 1; i <= K; i++)
        if (!found[i])
            cout << i << endl;*/
    //for (int i = 1; i <= N; i++)
    //  cout << i << ' ' << cnt[i] << ' ' << cnt2[i] << endl;
    while (tc--)
    {
        int kk;
        cin >> kk;
        cout << phi[kk + 2] << '\n';
        for (int i = 1; i <= solLength[kk]; i++)
        {
            if (sol[kk] & (1 << i))
                cout << 1 << ' ';
            else
                cout << 0 << ' ';
        }
        cout << '\n';
    }
    return 0;
}

Compilation message

binary.cpp: In function 'void bkt(int, int, int)':
binary.cpp:34:98: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   34 |             if(solLength[sumdp] != 0 && (solLength[sumdp] + 2 < pz or solLength[sumdp] + 2 == pz and rand() % bulan == 0))
      |                                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6772 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 12156 KB Output is correct
2 Correct 542 ms 11968 KB Output is correct
3 Correct 526 ms 12116 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 11972 KB Output is correct
2 Correct 576 ms 11972 KB Output is correct
3 Correct 618 ms 11972 KB Output is correct