oj.uz

Submission #197178

# Submission time Handle Problem Language Result Execution time Memory
197178 2020-01-19T16:03:28 Z Redhood Hidden Sequence (info1cup18_hidden) C++14
100 / 100
 7 ms 396 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct: Maximum length of a query = 5
2 Correct 2 ms 276 KB Output is correct: Maximum length of a query = 6
3 Correct 2 ms 248 KB Output is correct: Maximum length of a query = 5
4 Correct 2 ms 380 KB Output is correct: Maximum length of a query = 5
5 Correct 2 ms 248 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct: Maximum length of a query = 83
2 Correct 7 ms 248 KB Output is correct: Maximum length of a query = 90
3 Correct 6 ms 376 KB Output is correct: Maximum length of a query = 96
4 Correct 5 ms 248 KB Output is correct: Maximum length of a query = 77
5 Correct 4 ms 312 KB Output is correct: Maximum length of a query = 95
6 Correct 4 ms 248 KB Output is correct: Maximum length of a query = 87
7 Correct 5 ms 376 KB Output is correct: Maximum length of a query = 97
8 Correct 5 ms 248 KB Output is correct: Maximum length of a query = 83
9 Correct 6 ms 248 KB Output is correct: Maximum length of a query = 101
10 Correct 6 ms 248 KB Output is correct: Maximum length of a query = 100
11 Correct 6 ms 248 KB Output is correct: Maximum length of a query = 96
12 Correct 5 ms 248 KB Output is correct: Maximum length of a query = 100
13 Correct 5 ms 396 KB Output is correct: Maximum length of a query = 101