#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
pii gcd(int a,int b){
if(a>b)swap(a,b);
if(a==1)return pii(1,b-a);
if(a==0)return pii(b,0);
pii snc=gcd(a,b%a);
//cout << "a: "<<a<<" b: "<<b<< " döndü: "<<snc.first<<"\n";
return pii(snc.first,snc.second+b/a);
}
int mn=1e7,mnel=-1;
void solve(int k){
mn=1e7,mnel=-1;
int sayi=0;
vector<int> don;
vector<int> snc;
for (int i = 1; i <=(k+2)/2+1 ; i++)
{
int fr=k+2-i;
pii d=gcd(fr,i);
//cout << "i: "<<i<<" fr: "<<fr<<" gcd: "<<d.first<<" cost: "<<d.second<<"\n";
if(d.first!=1)continue;
if(d.second<mn)
{
mn=d.second,mnel=i;
}
sayi++;
}
//cout << "mn: "<<mn<<" mnel: "<<mnel<<"\n";
int a=mnel,b=k+2-mnel;
if(a>b)swap(a,b);
int prt=0;
while(a!=0){
if(a==1){
for(int i=1;i<=b-a;i++)snc.push_back(prt);
break;
}
for (int i = 0; i < b/a; i++)
{
snc.push_back(prt);
}
b=b%a;
swap(a,b);
prt=(prt+1)%2;
}
cout <<sayi<<"\n";
for(auto u: snc)cout << u<<" ";
cout <<"\n";
}
int main(){
int q;
cin>>q;
for (int i = 0; i < q; i++)
{
int k;
cin>>k;
solve(k);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
742 ms |
484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
