#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000
#define MOD 1000000007
#define N 1000006
#define MAX 10000006
#define LOG 30
using namespace std;
int n,t;
stack<bool> s;
int exg(int x,int y,bool pr) {
if(x==0 || y==0) return -1;
if(x<y) {
int totd=y/x;
int rem=y%x;
if(pr) for(int i=1;i<=totd;i++) s.push(0);
return exg(x,rem,pr)+totd;
}
else {
int totd=x/y;
int rem=x%y;
if(pr) for(int i=1;i<=totd;i++) s.push(1);
return exg(rem,y,pr)+totd;
}
}
void solve(int n) {
int k=n+2;
int ans=0;
int best=inf;
int x,y;
for(int i=1;i<=k/2;i++) {
if(__gcd(i,k-i)==1) {
++ans;
int step=exg(i,k-i,0);
if(step<best) {
best=step;
x=i,y=k-i;
}
}
}
printf("%d\n",ans*2);
exg(x,y,1);
s.pop();
while(sz(s)) {printf("%d ",s.top());s.pop();}
puts("");
}
int main() {
//freopen("input.txt","r",stdin);
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
solve(n);
}
}
Compilation message
binary.cpp: In function 'int main()':
binary.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&t);
~~~~~^~~~~~~~~
binary.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
binary.cpp: In function 'void solve(int)':
binary.cpp:84:5: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
exg(x,y,1);
~~~^~~~~~~
binary.cpp:84:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
488 KB |
Output is correct |
| 2 |
Correct |
116 ms |
488 KB |
Output is correct |
| 3 |
Correct |
111 ms |
488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
