Submission #98556

#	Time	Username	Problem	Language	Result	Execution time	Memory
98556		TAMREF	Binary Subsequences (info1cup17_binary)	C++11	100 / 100	551 ms	512 KiB

binary

#include <bits/stdc++.h>
using namespace std;
int t, k;

void pro(int k){
    int cnt = 0;
    int len = INT_MAX, lenx = 0;
    for(int i = 0; i + i < k; i++){
        int x = i, y = k - x;
        int nlen = 0;
        while(x){
            if(x == y){
                nlen = INT_MAX;
                break;
            }
            nlen += y / (x+1);
            y %= (x+1);
            swap(x,y);
        }
        if(nlen < INT_MAX) cnt += 2, nlen += y;
        if(nlen < len){
            len = nlen;
            lenx = i;
        }
    }
    cout << cnt << '\n';
    int X = lenx, Y = k - X;
    while(X || Y){
        cout << (X < Y) << ' ';
        if(X < Y) Y -= (X+1);
        else X -= (Y+1);
    }
    cout << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(cin >> t; t--;){
        cin >> k;
        pro(k);
    }
}

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