| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 270527 | s0m30n3 | Binary Subsequences (info1cup17_binary) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ppb pop_back
#define st first
#define nd second
#define ll long long
#define inf 1000000000
#define MOD 1000000007
#define LOG 40
#define EPS 0.000000001
#define MAX 1000005
using namespace std;
int solve_reverse(int fix_0, int fix_1) {
/*
Our base case is dp[0][0] = dp[0][1] = 0
*/
int n = 0;
while(max(fix_0, fix_1) > 0) {
/* The condition of while loop
indicates whether we reached
the base case mentioned above
*/
if(fix_0 == fix_1) {
/*
This line basically says
it is impossible to have such
situation.
Because both
fix_0 + 1 > fix_1 and
fix_1 + 1 > fix_0.
So this is a non-reachable
state.
*/
return inf;
}
if(fix_0 > fix_1) {
n += fix_0 / (fix_1 + 1);
/* This line speeds up the operations
which are decreasing fix_1 + 1 from
fix_0 whenever the 'if' condition is
satisfied.
*/
fix_0 %= fix_1 + 1;
/* this line gives us the result of the
sped up process.
*/
}
else {
n += fix_1 / (fix_0 + 1);
// similar
fix_1 %= fix_0 + 1;
// similar
}
}
// yeah, we found n !!!
return n;
}
void solve() {
int k, tot = 0, best = inf;
int dp_fix_0 = -1;
cin >> k;
// fix dp[n][0]
for(int dp_0 = 0; dp_0 <= k; dp_0++) {
/* automatically
dp[n][1] = k - dp[n][0]
*/
int n = solve_reverse(dp_0, k - dp_0);
/* now we have 'n' which is
the length of the string
if dp[n][0] was fixed like that
*/
if(n != inf) {
// if this dp[n][0] is valid
tot++;
if(n < best) {
// if this n is smallest
best = n;
dp_fix_0 = dp;
}
}
}
cout << tot << "\n";
if(tot == 0) {
cout << -1 << "\n";
return ;
}
// let's simulate the solve_reverse function
int dp_fix_1 = k - dp_fix_0;
vector<char> result;
while(max(dp_fix_0, dp_fix_1) > 0) {
/* this section is the straightforward
implementation of the
'solve_reverse' function.
*/
if(dp_fix_0 > dp_fix_1) {
dp_fix_0 -= dp_fix_1 + 1;
result.pb('0');
}
else {
dp_fix_1 -= dp_fix_0 + 1;
result.pb('1');
}
}
reverse(result.begin(), result.end());
// reverse the result because we reverse the actual process
for(auto c: result)
cout << c << " ";
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(t--)
solve();
}