oj.uz

Submission #388439

# Submission time Handle Problem Language Result Execution time Memory
388439 2021-04-11T14:15:23 Z keta_tsimakuridze Binary Subsequences (info1cup17_binary) C++14
100 / 100
 664 ms 452 KB 
#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

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

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 452 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 204 KB Output is correct
2 Correct 56 ms 204 KB Output is correct
3 Correct 54 ms 204 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 204 KB Output is correct
2 Correct 664 ms 204 KB Output is correct
3 Correct 651 ms 304 KB Output is correct