#include <bits/stdc++.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 N 100005
#define int long long
const int INF = 1e9 + 7;
int newgcd(int a, int b)
{
if (a < b) swap(a, b);
if (b == 1) return a - 1;
return gcd(b, a % b) + a / b;
}
void print(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';
print(j, i % j, 1 - turn, s);
}
int32_t main()
{
//fileio();
fastio();
int t;
cin>>t;
for (int i = 1; i <= t; i++)
{
int k;
cin>>k;
k += 2;
int ans = 0;
pii tmp;
int mini = INF;
for (int j = 1; j < k; j++)
{
int l = k - j;
if (gcd(j, l) != 1) continue;
ans++;
int gh = newgcd(l, j);
if (mini > gh)
{
mini = gh;
tmp = {j, l};
}
}
cout<<ans<<endl;
string s;
print(tmp.st, tmp.nd, 0, s);
reverse(s.begin(), s.end());
for (auto i : s) cout<<i<<sp;
cout<<endl;
}
cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
990 ms |
4672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
