oj.uz

Submission #389470

# Submission time Handle Problem Language Result Execution time Memory
389470 2021-04-14T06:31:53 Z balbit Binary Subsequences (info1cup17_binary) C++14
100 / 100
 729 ms 332 KB 
#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.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 332 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 204 KB Output is correct
2 Correct 69 ms 292 KB Output is correct
3 Correct 59 ms 204 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 292 KB Output is correct
2 Correct 729 ms 296 KB Output is correct
3 Correct 702 ms 208 KB Output is correct