oj.uz

Submission #67926

# Submission time Handle Problem Language Result Execution time Memory
67926 2018-08-15T14:22:37 Z tatatan Binary Subsequences (info1cup17_binary) C++11
100 / 100
 801 ms 676 KB 
#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.0 / 43.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 404 KB Output is correct
2 Correct 70 ms 424 KB Output is correct
3 Correct 65 ms 628 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 628 KB Output is correct
2 Correct 789 ms 672 KB Output is correct
3 Correct 768 ms 676 KB Output is correct