Submission #649476

#TimeUsernameProblemLanguageResultExecution timeMemory
649476dozerBinary Subsequences (info1cup17_binary)C++17
82 / 100
902 ms340 KiB
#include <bits/stdc++.h> //#include "c2.h" using namespace std; #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define pb push_back #define sp " " #define endl "\n" #define pii pair<int, int> #define st first #define nd second #define int long long #define N 100005 const int INF = 1e9 + 7; int newgcd(int a, int b) { if (a < b) swap(a, b); if (b == 1) return a - 1; return newgcd(b, a % b) + a / b; } void print2(int i, int j, int turn, string &s) { if (i < j) swap(i, j); if (j == 1) { for (int k = 1; k < i; k++) s += (char)turn + '0'; return; } for (int k = 0; k < i / j; k++) s += (char)turn + '0'; print2(j, i % j, 1 - turn, s); } void solve(int k) { pii tmp; int mini = INF, res = 0; k += 2; for (int j = 1; j < k; j++) { int l = k - j; if (gcd(j, l) != 1) continue; res++; int gh = newgcd(l, j); if (mini > gh) { mini = gh; tmp = {j, l}; } } cout<<res<<endl; string s; print2(tmp.st, tmp.nd, 0, s); for (auto i : s) cout<<i<<sp; cout<<endl; } int32_t main() { //fileio(); fastio(); int t; cin>>t; while(t--) { int k; cin>>k; solve(k); } cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...