제출 #270524

#제출 시각아이디문제언어결과실행 시간메모리
270524Atill83Binary Subsequences (info1cup17_binary)C++14
100 / 100
349 ms504 KiB
#include <bits/stdc++.h> #define ff first #define ss second using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 3e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n; int gcd(int a, int b){ if(a == b){ return mod; } int st = 0; if(b > a) swap(a, b); while(b){ st += a / (b + 1); a %= (b + 1); swap(a, b); if(a == b) return mod; } if(a){ return st + a; }else { return mod; } } void solve(){ ll k; cin>>k; ll ans = 0; int mnSt = mod; int mnx = -1; for(int i = 0; i <= k / 2; i++){ int st = gcd(i, k - i); if(st <= k + 1){ ans += 2; if(st < mnSt){ mnSt = st; mnx = i; } } } cout<<ans<<endl; int x = mnx, y = k - mnx; vector<int> res; while(x || y){ if(x > y){ res.push_back(1); x = x - (y + 1); }else{ res.push_back(0); y = y - (x + 1); } } for(int j = res.size() - 1; j >= 0; j--) cout<<res[j]<<" "; cout<<endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif int t; cin>>t; while(t--) solve(); #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...