oj.uz

Submission #388437

# Submission time Handle Problem Language Result Execution time Memory
388437 2021-04-11T14:12:00 Z keta_tsimakuridze Binary Subsequences (info1cup17_binary) C++14
82 / 100
 900 ms 448 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#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(){
	// 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:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 |  main(){
      |       ^

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 448 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 204 KB Output is correct
2 Correct 111 ms 204 KB Output is correct
3 Correct 112 ms 292 KB Output is correct

Subtask #3
0 / 18.0

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