Submission #67926

#	Time	Username	Problem	Language	Result	Execution time	Memory
67926		tatatan	Binary Subsequences (info1cup17_binary)	C++11	100 / 100	801 ms	676 KiB

binary

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

pii gcd(int x,int y) {

	if(x<y) swap(x,y);
	if(y==0) return mp(x,0);
	pii ret=gcd(y,x%y);
	ret.nd+=(x/y);
	return ret;

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--) {
		int k,cnt=0,a1=-1,a2,mn=10000000;
		pii t;
		cin>>k;
		for(int i=1;i<=k+1&&i<k-i+2;++i) {
			t=gcd(i,k-i+2);
			if(t.st==1) {
				cnt+=2;
				if(a1==-1||mn>t.nd) {
					a1=i; a2=k-i+2; mn=t.nd;
				}
			}
		}
		cout<<cnt<<endl;
		while(a1!=1||a2!=1) {
			if(a1>a2) {
				a1-=a2;
				cout<<0<<" ";
			}
			else {
				a2-=a1;
				cout<<1<<" ";
			}
		}
		cout<<endl;
	}

}

• Subtask 1: 43 / 43
• Subtask 2: 39 / 39
• Subtask 3: 18 / 18