Submission #197178

#	Time	Username	Problem	Language	Result	Execution time	Memory
197178		Redhood	Hidden Sequence (info1cup18_hidden)	C++14	100 / 100	7 ms	396 KiB

hidden

#include<bits/stdc++.h>
#include "grader.h"

using namespace std;


#define pb push_back
#define len(x) (int)(x).size()

bool is(vector<int>q){
 	#ifdef LOCAL
 		cout << len(q) << '\n';
 		for(auto u : q)cout << u << ' ';
 		cout << '\n';
 	#endif
 	if(q.empty()){
    	#ifdef LOCAL
    		cout << "true\n";
    	#endif               
    	return true;
	}
 	bool ans=  isSubsequence(q);
 	#ifdef LOCAL
 	if(ans)cout<<"true\n";
 	else cout<<"false\n";
 	#endif
 	return ans;
}

vector < int > findSequence (int N)
{
    vector < int > ans(N);
    int mx = N / 2;
   	vector < int > que;
   	for(int i = 0 ; i < mx; ++i)que.pb(1);
   	int bt = 1;
   	if(isSubsequence(que)){
   	 	// it means that  we have  half part of 1 but not 0
   	 	// let's binary cnt of zeros
   		bt ^= 1;
   	}
   	int l = 0 , r = N - mx + 1;
   	while(l != r){
   	 	int mid = (l + r) >> 1;
   	 	vector<int>q;
   	 	for(int f = 0 ; f < mid; ++f)q.pb(bt);
   	 	if(is(q)){
   	 	 	if(l + 1 == r)l = r;
   	 	 	else l = mid;
   	 	}else r = mid;
   	}
   	vector < int > cnt(2) , done(2);
   	cnt[bt] = r - 1 , cnt[bt^1] = N - cnt[bt];

 //  	cout << "CNT : " << cnt[0] << ' ' << cnt[1] << '\n';

   	for(int i = N - 1; i >=0 ;--i){
   	 	if(!cnt[0]){ans[i]=1,cnt[1]--;continue;}
   	 	if(!cnt[1]){ans[i]=0,cnt[0]--;continue;}
   	 	bt = 1;
   	 	if(cnt[0] + done[1] > cnt[1] + done[0])bt ^= 1;
   	 	vector<int>q;
   	 	for(int x = 0; x < cnt[bt^1];++x)q.pb(bt^1);
   	 	q.pb(bt);
   	 	for(int x = 0 ; x < done[bt];++x)q.pb(bt);
   	 	ans[i] = (!is(q))^bt;
   	 	done[ans[i]]++ , cnt[ans[i]]--;
   	}
    return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     fprintf (fifo_out, "%d\n", ans.size ());
                                ~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size () && i < N; i++)
                   ~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80