oj.uz

Submission #199054

# Submission time Handle Problem Language Result Execution time Memory
199054 2020-01-28T20:08:08 Z Redhood Binary Subsequences (info1cup17_binary) C++14
100 / 100
 615 ms 388 KB 
#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.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 376 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 376 KB Output is correct
2 Correct 55 ms 376 KB Output is correct
3 Correct 53 ms 376 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 380 KB Output is correct
2 Correct 611 ms 384 KB Output is correct
3 Correct 606 ms 388 KB Output is correct