Submission #68155

#	Time	Username	Problem	Language	Result	Execution time	Memory
68155		quoriess	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	727 ms	624 KiB

binary

#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 / 43
• Subtask 2: 39 / 39
• Subtask 3: 18 / 18