Submission #199054

#	Time	Username	Problem	Language	Result	Execution time	Memory
199054		Redhood	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	615 ms	388 KiB

binary

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int inf = 1e9+7;
int answer(int a , int b){
    int ans=0;
    while(b){
        int c=a%(b+1);
        if(c == b) return inf;
        ans+=a/(b+1);
        a = b , b = c;
    }
    ans+=a/(b+1);
    return ans;
}

vector<int> answer_lul(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){
    int len=inf , pr = 0, ans=0;
    for(int prev=0;prev<=k;++prev){
        if(prev>=k-prev)break;
        int now=answer(k-prev, prev);
        if(now!=inf)ans++;
        if(now<len){
            len = now, pr=prev;
        }
    }
    if(len==inf)return{0,{}};
    vector<int>x={k-pr,pr};
    return {ans , answer_lul(x)};
}
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: 18 / 18