Submission #917214

#	Time	Username	Problem	Language	Result	Execution time	Memory
917214		andrei_iorgulescu	Binary Subsequences (info1cup17_binary)	C++14	43 / 100	842 ms	68220 KiB

binary

#include <bits/stdc++.h>

using namespace std;

const int N = 26;
const int K = 100000;

int a[N + 5];
vector<int>sol[10 * K + 5];
int dp0,dp1,sumdp;

void afis(int M)
{
    if (sol[sumdp].size() == 0 or M < sol[sumdp].size())
    {
        sol[sumdp].clear();
        for (int i = 1; i <= M; i++)
            sol[sumdp].push_back(a[i]);
    }
}

void bkt(int pos,int pz,int sumant)
{
    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[pz + lung - 1] = 0;
                    sumdp = lung;
                    bkt(pos + 1,lung + 1,lung);
                }
            }
            else
            {
                dp0 += sumant;
                for (int lung = 1; lung <= N - pz + 1; lung++)
                {
                    a[pz + lung - 1] = 0;
                    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[pz + lung - 1] = 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 - 1) / i;
}


signed main()
{
    //for (int i = 1; i <= N; i++)
      //  found[i] = true;
    bkt(1,1,0);
    //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;
    int tc;
    cin >> tc;
    while (tc--)
    {
        int kk;
        cin >> kk;
        cout << phi[kk + 2] << '\n';
        for (auto it : sol[kk])
            cout << it << ' ';
        cout << '\n';
    }
    return 0;
}

Compilation message (stderr)

binary.cpp: In function 'void afis(int)':
binary.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     if (sol[sumdp].size() == 0 or M < sol[sumdp].size())
      |                                   ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 43 / 43
• Subtask 2: 0 / 39
• Subtask 3: 0 / 18