Submission #389556

#TimeUsernameProblemLanguageResultExecution timeMemory
389556cheissmartBinary Subsequences (info1cup17_binary)C++14
100 / 100
673 ms332 KiB
#include <bits/stdc++.h> #define F first #define S second #define V vector #define PB push_back #define EB emplace_back #define MP make_pair #define ALL(v) (v).begin(), (v).end() #define debug(x) cerr << "LINE(" << __LINE__ << "): " << #x << " is " << (x) << endl using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; const int INF = 1e9 + 7, N = 2e3 + 7, M = 1e9 + 7; void add(int& a, int b) { a += b; if(a >= M) a -= M; } int go(int a, int b) { if(a == 0 && b == 0) return 1; if(a == b) return 0; if(a < b) swap(a, b); return go(a % (b + 1), b); } int go_len(int a, int b) { if(a == 0 && b == 0) return 0; if(a == b) return INF; if(a < b) swap(a, b); return go_len(a % (b + 1), b) + a / (b + 1); } signed main() { ios::sync_with_stdio(0), cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i++) { int k; cin >> k; int ans = 0, mn_len = INF, j = -1; for(int i = 0; i <= k / 2; i++) { add(ans, go(i, k - i) * 2 % M); int len = go_len(i, k - i); if(len < mn_len) { mn_len = len; j = i; } } cout << ans << '\n'; int x = j, y = k - j; while(true) { if(x > y) cout << 0, x -= y + 1; else cout << 1, y -= x + 1; if(x || y) cout << ' '; else break; } cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...