Submission #389470

#	Time	Username	Problem	Language	Result	Execution time	Memory
389470		balbit	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	729 ms	332 KiB

binary

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
//#ifndef BALBIT
//#include "grader.h"
//#endif

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBITs

int stp = 0;

bool yes(int a, int b) {
    if (a==b) return a==0;
    if (a < b) swap(a,b);
    stp += (a/(b+1));
    a %= (b+1);
    return yes(a,b);
}

string mo;

void go2(int a, int b){
    if (a==b) return;
    if (a<b) {
        mo.pb('1');
        b-=a+1;
        go2(a,b);
    }else{
        mo.pb('0');
        a-=b+1;
        go2(a,b);
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int t; cin>>t;
    while (t--) {
        int n; cin>>n;
        int re = 0;
        int sht = 100000000;
        int ho = -1;
        for (int i = 0; i<=n; ++i) {
            stp = 0;
            if (yes(i, n-i)) {
                ++re;
                if (stp < sht) {
                    sht = stp;
                    ho = i;
                }
            }
        }
        cout<<re<<endl;
        mo.clear();
        go2(ho, n-ho);
        for (char c : mo) cout<<c<<' ';
        cout<<endl;
    }
}

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