oj.uz

Submission #388438

# Submission time Handle Problem Language Result Execution time Memory
388438 2021-04-11T14:13:12 Z keta_tsimakuridze Binary Subsequences (info1cup17_binary) C++14
82 / 100
 900 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;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<<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 150 ms 452 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 204 KB Output is correct
2 Correct 113 ms 308 KB Output is correct
3 Correct 107 ms 312 KB Output is correct

Subtask #3
0 / 18.0

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