oj.uz

Submission #68155

# Submission time Handle Problem Language Result Execution time Memory
68155 2018-08-16T07:15:03 Z quoriess Binary Subsequences (info1cup17_binary) C++14
100 / 100
 727 ms 624 KB 
#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 ; 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*2<<"\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;
}

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 376 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 488 KB Output is correct
2 Correct 67 ms 488 KB Output is correct
3 Correct 63 ms 488 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 576 KB Output is correct
2 Correct 708 ms 624 KB Output is correct
3 Correct 705 ms 624 KB Output is correct