Submission #389965

#TimeUsernameProblemLanguageResultExecution timeMemory
389965abc864197532Binary Subsequences (info1cup17_binary)C++17
82 / 100
1098 ms332 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define pb push_back #define eb emplace_back #define mp make_pair #define test(x) cout << #x << ' ' << x << endl #define printv(x) { \ for (auto a : x) cout << a << ' '; \ cout << endl; \ } #define pii pair<int, int> #define pll pair<lli, lli> #define X first #define Y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() const int N = 512, abc = 864197532; int chk(int l, int r) { int len = 0; while (l > 1 && r > 1) { len++; if (l > r) { l -= r; } else { r -= l; } } return len + r + l - 2; } string gen(int l, int r) { string ans; while (l > 1 || r > 1) { if (l > r) { ans += "1 "; l -= r; } else { ans += "0 "; r -= l; } } return ans; } int main () { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { int x; cin >> x; int ans1 = 0, ans2 = 1 << 30, bestl = -1; for (int l = 1; l < x + 2 - l; ++l) if (__gcd(l, x + 2 - l) == 1) { int re = chk(l, x + 2 - l); ans1++; if (ans2 > re) { bestl = l; ans2 = re; } } cout << ans1 * 2 << '\n' << gen(bestl, x + 2 - bestl) << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...