Submission #45372

#	Time	Username	Problem	Language	Result	Execution time	Memory
45372		model_code	Binary Subsequences (info1cup17_binary)	C++17	100 / 100	896 ms	692 KiB

binary

#include<bits/stdc++.h>

using namespace std;

int Tests, ans[1000009];

void solve (int K)
{
    int cnt = 0, minL = K + 2, how = -1;
    for (int T = 0; T <= K - T; T++)
    {
        int i = T, j = K - T, currL = 0;
        bool fail = 0;
        while (i > 0 || j > 0)
        {
            if (i < 0 || j < 0)
            {
                fail = 1;
                break;
            }
            if (i < j) swap (i, j);
            int curr = (i - j - 1) / (j + 1) + 1;
            i -= curr * (j + 1), currL += curr;
        }
        if (!fail)
        {
            cnt ++;
            if (T != K - T) cnt ++;
            if (currL < minL)
                minL = currL, how = T;
        }
    }
    printf ("%d\n", cnt), ans[0] = 0;
    int i = how, j = K - how;
    while (i > 0 || j > 0)
    {
        if (i > j) i = i - j - 1, ans[++ans[0]] = 1;
        else j = j - i - 1, ans[++ans[0]] = 0;
    }
    for (int i=ans[0]; i>=1; i--)
        printf ("%d ", ans[i]);
    printf ("\n");
}
int main ()
{

scanf ("%d", &Tests);
for (int i=1; i<=Tests; i++)
{
    int x;
    scanf ("%d", &x);
    solve (x);
}

return 0;
}

Compilation message (stderr)

binary.cpp: In function 'int main()':
binary.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &Tests);
 ~~~~~~^~~~~~~~~~~~~~
binary.cpp:51:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &x);
     ~~~~~~^~~~~~~~~~

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