oj.uz

Submission #67925

# Submission time Handle Problem Language Result Execution time Memory
67925 2018-08-15T14:21:00 Z tatatan Binary Subsequences (info1cup17_binary) C++11
82 / 100
 900 ms 560 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;
		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.0 / 43.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 376 KB Output is correct
2 Correct 193 ms 560 KB Output is correct
3 Correct 177 ms 560 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 560 KB Time limit exceeded
2 Halted 0 ms 0 KB -