Submission #1140102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140102		12345678	Binary Subsequences (info1cup17_binary)	C++20	100 / 100	255 ms	436 KiB

binary

#include <bits/stdc++.h>

using namespace std;

int Q, k;

int solve(int a, int b)
{
    if (a==1) return b-1;
    if (b==1) return a-1;
    if (a>=b)
    {
        int mod=a%b, div=a/b;
        if (mod==0) return -1e9;
        return div+solve(mod, b);
    }
    else
    {
        int mod=b%a, div=b/a;
        if (mod==0) return -1e9;
        return div+solve(a, mod);
    }
}

void printans(int a, int b)
{
    if (a==1&&b==1) return;
    if (a>b) return cout<<1<<' ', printans(a-b, b), void();
    else return cout<<0<<' ', printans(a, b-a), void();
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>Q;
    while (Q--)
    {
        cin>>k;
        k+=2;
        int cnt=0;
        pair<int, int> ans={1e9, 0}; 
        for (int a=1; a<k-a; a++)
        {
            //cout<<"debug "<<a<<' '<<k-a<<' '<<solve(a, k-a)<<'\n';
            int tmp=solve(a, k-a);
            if (tmp>=0) cnt++, ans=min(ans, {tmp, a});
        }

        cout<<2*cnt<<'\n';
        printans(ans.second, k-ans.second);
        cout<<'\n';
    }
}

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