Submission #389986

#TimeUsernameProblemLanguageResultExecution timeMemory
389986wiwihoBinary Subsequences (info1cup17_binary)C++14
100 / 100
682 ms324 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define pb(a) push_back(a) #define eb(a) emplace_back(a) #define pf(a) push_front(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get<i>(t) #define tomax(a, b) ((a) = max((a), (b))) #define tomin(a, b) ((a) = min((a), (b))) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } int main(){ StarBurstStream int T; cin >> T; while(T--){ int k; cin >> k; int mn = k, mnp = 1; int ans = 0; for(int _z = 1; _z + 1 <= k + 2; _z++){ int z = _z; int o = k + 2 - z; if(z >= o) break; if(__gcd(o, z) != 1) continue; ans += 2; int cnt = 0; while(o > 0 && z > 0){ if(o > z){ cnt += o / z; o %= z; } else{ cnt += z / o; z %= o; } } cnt--; if(cnt < mn){ mn = cnt; mnp = _z; } } // cerr << mn << " " << mnp << "\n"; int z = mnp, o = k + 2 - z; vector<int> s; while(o > 0 && z > 0){ // cerr << o << " " << z << "\n"; if(o > z){ o -= z; s.eb(0); } else{ z -= o; s.eb(1); } } s.pob; cout << ans << "\n"; printv(s, cout); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...