Submission #916751

#	Time	Username	Problem	Language	Result	Execution time	Memory
916751		andrei_iorgulescu	Binary Subsequences (info1cup17_binary)	C++14	0 / 100	3 ms	1636 KiB

binary

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 4;
const int K = 2000;

int cnt[10 * K + 5];
bool found[10 * K + 5];
int a[N + 5];
vector<int>sol[10 * 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)
    {
        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;
    }
    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] == 0)
        {
            sumdp += d0;
            if (a[i - 2] == 1)
                sumdp += d1;
        }
        else
        {
            sumdp += d1;
            if (a[i - 2] == 0)
                sumdp += d0;
        }
        if (sumdp > K)
            return;
        if (a[i] == 0 and a[i - 1] == 1)
            d0 += d1;
        else if (a[i] == 1 and a[i - 1] == 0)
            d1 += d0;
        found[sumdp] = true;
    }
    found[sumdp] = true;
    /*for (int i = 1; i <= M; i++)
        cout << a[i] << ' ';
    cout << sumdp << 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)
{
    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);
        }
    }
    else
    {
        if (pos % 2 == 1)
        {
            for (int len = 1; sdp <= K; len++)
            {
                dp0 += dp1;
                sdp += dp0;
                bktsus(pos + 1);
            }
        }
        else
        {
            for (int len = 1; sdp <= K; len++)
            {
                if (dp1 == 0)
                {
                    dp1 = sdp + 1;
                    sdp += sdp + 1;
                    bktsus(pos + 1);
                }
                else
                {
                    dp1 += dp0;
                    sdp += dp1;
                    bktsus(pos + 1);
                }
            }
        }
    }
}

signed main()
{
    for (int i = 1; i <= N; i++)
        found[i] = true;
    bkt(1);
    //bktsus(1);
    for (int i = 1; i <= K; i++)
        cnt[i] = 2 * cnt[i];
    int tc;
    cin >> tc;
    while (tc--)
    {
        int kk;
        cin >> kk;
        cout << -1 << '\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:26: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]
   26 |         if (sol[p - 1].size() == 0 or M < sol[p - 1].size())
      |                                       ~~^~~~~~~~~~~~~~~~~~~
binary.cpp:64: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]
   64 |     if (sol[sumdp].size() == 0 or M < sol[sumdp].size())
      |                                   ~~^~~~~~~~~~~~~~~~~~~

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