Submission #67925

#	Time	Username	Problem	Language	Result	Execution time	Memory
67925		tatatan	Binary Subsequences (info1cup17_binary)	C++11	82 / 100	1065 ms	560 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;
		cin>>k;
		for(int i=1;i<=k+1&&i<k-i+2;++i)
			if(gcd(i,k-i+2).st==1) {
				cnt+=2;
				if(a1==-1||gcd(a1,a2).nd>gcd(i,k-i+2).nd) {
					a1=i; a2=k-i+2;
				}
			}
		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: 0 / 18