Submission #916804

#	Time	Username	Problem	Language	Result	Execution time	Memory
916804		andrei_iorgulescu	Binary Subsequences (info1cup17_binary)	C++14	43 / 100	131 ms	2640 KiB

binary

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 20;
const int K = 2000;

int cnt[10 * K + 5];
int cnt2[10 * K + 5];
bool found[10 * K + 5];
int a[N + 5];
vector<int>sol[10 * K + 5];
int dp[K + 5];

void afis(int M)
{
    int sumdp = 1,d0 = 0,d1 = 0;
    int p;
    for (p = 2; p <= M; p++)
    {
        if (a[p] != a[p - 1])
            break;
    }
    if (p == M + 1)
    {
        cnt2[M]++;
        if (sol[p - 1].size() == 0 or M < sol[p - 1].size())
        {
            sol[p - 1].clear();
            for (int i = 1; i <= M; i++)
                sol[p - 1].push_back(a[i]);
        }
        return;
    }
    for (int i = 1; i < p; i++)
        dp[i] = 1;
    dp[p] = p;
    if (a[1] == 1)
        d1 = 1,d0 = p,sumdp = 2 * p - 1;
    else
        d1 = p,d0 = 1,sumdp = 2 * p - 1;
    for (int i = p + 1; i <= M; i++)
    {
        if (a[i] == 1)
        {
            int j = i - 1;
            while (j > 0 and a[j] == 0)
                d1 += dp[j],j--;
            dp[i] = d1;
        }
        else
        {
            int j = i - 1;
            while (j > 0 and a[j] == 1)
                d0 += dp[j],j--;
            dp[i] = d0;
        }
        if (a[i] == 0)
            sumdp += d0;
        else
            sumdp += d1;
        if (sumdp > K)
            return;
        found[sumdp] = true;
    }
    found[sumdp] = true;
    cnt2[sumdp]++;
    /*if (sumdp == 5)
    {
        for (int i = 1; i <= M; i++)
            cout << a[i] << ' ';
        cout << endl;
    }*/
    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)
{
    if (pos != 1)
        afis(pos - 1);
    if (pos == N + 1)
        return;
    else
    {
        a[pos] = 0;
        bkt(pos + 1);
        a[pos] = 1;
        bkt(pos + 1);
    }
}

int sdp,dp0,dp1;

void bktsus(int pos,int pz,int sumant)
{
    //cout << pos << ' ' << pz << ' ' << sumant << ' ' << sdp << endl;
    if (sdp > K)
        return;
    cnt[sdp]++;
    if (pos == 1)
    {
        for (int len = 1; len <= K; len++)
        {
            sdp = len;
            dp0 = 1;
            dp1 = 0;
            bktsus(pos + 1,len + 1,len);
            //cout << len << endl;
        }
    }
    else
    {
        if (pos % 2 == 1)
        {
            int ret_sdp = sdp;
            int ret_dp1 = dp1;
            int ret_dp0 = dp0;
            dp0 += sumant;
            sdp += dp0;
            bktsus(pos + 1,pz + 1,dp0);
            for (int len = 2; sdp <= K; len++)
            {
                sdp += dp0;
                bktsus(pos + 1,pz + len,len * dp0);
            }
            sdp = ret_sdp;
            dp0 = ret_dp0;
            dp1 = ret_dp1;
        }
        else
        {
            int ret_sdp = sdp;
            int ret_dp0 = dp0;
            int ret_dp1 = dp1;
            if (pos == 2)
                dp1 = 1;
            dp1 += sumant;
            sdp += dp1;
            bktsus(pos + 1,pz + 1,dp1);
            for (int len = 2; sdp <= K; len++)
            {
                sdp += dp1;
                bktsus(pos + 1,pz + len,len * dp1);
            }
            sdp = ret_sdp;
            dp0 = ret_dp0;
            dp1 = ret_dp1;
        }
    }
}

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

Compilation message (stderr)

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

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