Submission #388439

#	Time	Username	Problem	Language	Result	Execution time	Memory
388439		keta_tsimakuridze	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	664 ms	452 KiB

binary

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,n,steps,ind;
string s;
bool check(int a,int b){	
	if(!max(a,b)) return 1;
	if(a==b) return 0;
	steps+=a/(b+1)+b/(a+1);
	return check(a%(b+1),b%(a+1));
}
 main(){
 	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	// t=1;
	cin >> t;
	while(t--){
		cin>>n;
		int mn=1e9,cnt=0;
		s=""; 
		for(int i=0;i<=n/2;i++){
			steps=0;
			if(check(i,n-i)) {
				cnt++;
				if(steps<mn) {
					mn=steps;
					ind=i;
				}
			}
 		}
 		int a=ind, b=n-ind;
 		while(max(a,b)){
 			if(a>b){
 				a-=b+1;
 				s+='0';
			 }
			 else b-=a+1,s+='1';
		 }
		 cout<<cnt*2<<endl;
		 for(int i=s.size()-1;i>=0;i--){
		 	cout<<s[i]<<" ";
		 }
		 cout<<endl;
	}
}

Compilation message (stderr)

binary.cpp:14:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 |  main(){
      |       ^

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