oj.uz

Submission #97768

# Submission time Handle Problem Language Result Execution time Memory
97768 2019-02-18T11:07:15 Z KLPP Binary Subsequences (info1cup17_binary) C++14
82 / 100
 900 ms 384 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;


int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int K;
		scanf("%d",&K);
		lld ans1=0;
		lld ans2=1000000000;
		vector<int> v;
		//cout<<-1<<endl;
		pii best;
		for(int t=0;t*2<K;t++){
			lld can=0;
			vector<int> seq;
			pii p=pii(t,K-t);
			while(p.first!=0 || p.second!=0){
				//cout<<p.first<<" "<<p.second<<endl;
				
				if(p.first>p.second){
					can+=p.first/(p.second+1);
					p.first%=(p.second+1);
				}
				else{
					if(p.first<p.second){
						can+=p.second/(p.first+1);
						p.second%=(p.first+1);
					}
					else{
						can=-1;
						break;
					}
				}
				
			}//cout<<t<<" "<<K-t<<" "<<can<<endl;
			if(can!=-1)ans1++;
			if(can<ans2 && can!=-1){
				best=pii(t,K-t);
				ans2=can;
			}
		}
		printf("%d\n",ans1*2);
		pii p=best;
		//cout<<best.first<<" "<<best.second<<endl;
		while(p.first!=0 || p.second!=0){
				//cout<<p.first<<" "<<p.second<<endl;
				
				if(p.first>p.second){
					p.first-=p.second+1;
					v.push_back(0);
				}
				else{
					if(p.first<p.second){v.push_back(1);
						p.second-=p.first+1;
					}
					else{
						
						break;
					}
				}
				
			}
		for(int i=0;i<v.size();i++)printf("%d ",v[i]);
		printf("\n");
	}
	return 0;
}

Compilation message

binary.cpp: In function 'int main()':
binary.cpp:48:23: warning: format '%d' expects argument of type 'int', but argument 2 has type 'lld {aka long long int}' [-Wformat=]
   printf("%d\n",ans1*2);
                 ~~~~~~^
binary.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++)printf("%d ",v[i]);
               ~^~~~~~~~~
binary.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&T);
  ~~~~~^~~~~~~~~
binary.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&K);
   ~~~~~^~~~~~~~~

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 356 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 384 KB Output is correct
2 Correct 79 ms 384 KB Output is correct
3 Correct 79 ms 384 KB Output is correct

Subtask #3
0 / 18.0

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