oj.uz

Submission #97763

# Submission time Handle Problem Language Result Execution time Memory
97763 2019-02-18T10:50:28 Z KLPP Binary Subsequences (info1cup17_binary) C++14
0 / 100
 900 ms 10592 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;
		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;
				can++;
				if(p.first>p.second)p.first-=p.second+1,seq.push_back(1);
				else{
					if(p.first<p.second)p.second-=p.first+1,seq.push_back(0);
					else{
						can=-1;
						break;
					}
				}
				
			}
			if(can!=-1)ans1++;
			if(can<ans2 && can!=-1){
				v.clear();
				for(int j=0;j<seq.size();j++)v.push_back(seq[j]);
				ans2=can;
			}
		}
		cout<<ans1<<endl;
		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:118:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<seq.size();j++)v.push_back(seq[j]);
                 ~^~~~~~~~~~~
binary.cpp:123:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
               ~^~~~~~~~~

Subtask #1
0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 764 KB Time limit exceeded

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 1844 KB Output is correct
2 Execution timed out 994 ms 2060 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

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