Submission #199053

#	Time	Username	Problem	Language	Result	Execution time	Memory
199053		Redhood	Binary Subsequences (info1cup17_binary)	C++14	82 / 100	1096 ms	760 KiB

binary

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int inf = 1e9+7;
vector<int> answer(vector<int>x){
    int pos=0;
    vector<int>ans;
    while(x.back()){
        x.pb(x[pos]%(x[pos+1]+1));
        if(x.back()==x[pos+1]){
            ans.pb(inf);
            return ans;
        }
        ans.pb(x[pos]/(x[pos+1]+1));
        ++pos;
    }
    ans.pb(x[pos]/(x[pos+1]+1));
    return ans;
}
pair < int , vector<int> > solve(int k){
    vector<int>currans;
    int len=inf , ans = 0;
    for(int prev=0;prev<=k;++prev){
        if(prev>=k-prev)break;
        vector<int>tryy={k-prev , prev};
        tryy=answer(tryy);
        long long  sum=0;for(auto u : tryy)sum+=u;
        if(sum < inf)ans++;
        if(sum<len){
            len=sum,currans=tryy;
        }
    }
//    cerr<<"ok\n";
    return {ans , currans};
}
signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0), cout.tie(0);
    int t;cin>>t;
    while(t--){
        int k;cin>>k;
        pair<int,vector<int>>answer=solve(k);
//        if(answer.fi==0){cout<<-1;continue;}
        cout<< answer.fi*2 << '\n';
        bool bt=0;
        for(auto u : answer.se){
            for(int z=0;z<u;++z)cout<<bt<<' ';
            bt^=1;
        }
        cout<<'\n';
    }
    return 0;
}

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