oj.uz

Submission #97764

# Submission time Handle Problem Language Result Execution time Memory
97764 2019-02-18T10:58:00 Z KLPP Binary Subsequences (info1cup17_binary) C++14
82 / 100
 900 ms 640 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
vector<int> ANSWER[2000];


int main(){
	/*int T;
	cin>>T;
	
	
	while(T--){
		int K;
		cin>>K;
		cout<<-1<<endl;*/
		
		/*for(int msk=0;msk<(1<<K);msk++){
			int arr[K];
			for(int i=0;i<K;i++)arr[i]=((msk&(1<<i))>0);
			lld DP[K];
			lld ans=0;
			for(int i=0;i<K;i++){
				DP[i]=0;
				bool b=true;
				for(int j=i-1;j>-1;j--){
					DP[i]+=DP[j];
					if(arr[j]==arr[i]){b=false;
						break;	
					}
				}DP[i]+=b;
				ans+=DP[i];
				//cout<<DP[i]<<endl;
			}cout<<ans<<" ";
			for(int i=0;i<K;i++)cout<<arr[i];
			cout<<endl;
		}*/
		
	//}
	for(int K=1;K<=16;K++){
		for(int msk=0;msk<(1<<K);msk++){
			int arr[K];
			for(int i=0;i<K;i++)arr[i]=((msk&(1<<i))>0);
			lld DP[K];
			lld ans=0;
			for(int i=0;i<K;i++){
				DP[i]=0;
				bool b=true;
				for(int j=i-1;j>-1;j--){
					DP[i]+=DP[j];
					if(arr[j]==arr[i]){b=false;
						break;	
					}
				}DP[i]+=b;
				ans+=DP[i];
				//cout<<DP[i]<<endl;
			}//cout<<ans<<" ";
			if(ans<=2000 && ANSWER[ans-1].size()==0){
				for(int i=0;i<K;i++)ANSWER[ans-1].push_back(arr[i]);
			}
			/*for(int i=0;i<K;i++)cout<<arr[i];
			cout<<endl;*/
		}
	}
	/*cout<<"#include<bits/stdc++.h>"<<endl;
	cout<<"using namespace std;"<<endl;
	cout<<"void answer(int K){"<<endl;
	for(int i=0;i<2000;i++){
		cout<<"if(K=="<<i+1<<"){"<<endl;
		cout<<"cout<< ";
		for(int j=0;j<ANSWER[i].size();j++)cout<<ANSWER[i][j]<<" << ' ' <<";
		cout<<"endl;";
		cout<<endl;
		cout<<"}"<<endl;
	}
	cout<<"}"<<endl;
	cout<<"int main(){"<<endl;
	cout<<"	int T;"<<endl;
	cout<<"	cin>>T;"<<endl;
	cout<<"	while(T--){"<<endl;
	cout<<"		int K;"<<endl;
	cout<<"		cin>>K;"<<endl;
	cout<<"		cout<<-1<<endl;"<<endl;
	cout<<"		 answer(K);"<<endl;
	cout<<"		}"<<endl;
	cout<<"	}"<<endl;
	cout<<"}"<<endl;*/
	int T;
	cin>>T;
	while(T--){
		int K;
		cin>>K;
		lld ans1=0;
		lld ans2=1000000000;
		vector<int> v;
		//cout<<-1<<endl;
		pii best;
		for(int t=0;t<=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;
			}
		}
		cout<<ans1<<endl;
		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++)cout<<v[i]<<" ";
		cout<<endl;
	}
	return 0;
}

Compilation message

binary.cpp: In function 'int main()':
binary.cpp:149:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
               ~^~~~~~~~~

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 640 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 512 KB Output is correct
2 Correct 173 ms 512 KB Output is correct
3 Correct 161 ms 512 KB Output is correct

Subtask #3
0 / 18.0

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