Submission #67264

#	Time	Username	Problem	Language	Result	Execution time	Memory
67264		ekrem	Hidden Sequence (info1cup18_hidden)	C++11	100 / 100	11 ms	688 KiB

hidden

#include <bits/stdc++.h>

#include "grader.h"
#define pb push_back
using namespace std;

typedef vector < int > vi;

static int maxQ = 0;
static vi theRealAnswer;

// bool isSubsequence (vi v){
// 	if (v.size () > maxQ)
// 		maxQ = v.size ();
// 	int i = 0;
// 	for (int j = 0; j < v.size(); j++){
// 		while (i < theRealAnswer.size () && v[j] != theRealAnswer[i]) i ++;
// 		if (i == theRealAnswer.size ()) return 0;
// 		i++;
// 	}
// 	return 1;
// }

int say[2] = {-1, -1}, x[2] = {0, 0}, n;

int sor(){

	vi sor;
	if(say[1] - x[1] + x[0] + 1 <= n/2 + 1){
		for(int i = 1; i <= x[0] + 1; i++)
			sor.pb(0);
		for(int i = 1; i <= say[1] - x[1]; i++)
			sor.pb(1);
		// for(int i = 0; i < sor.size(); i++)cout << sor[i] << " ,";cout << endl;
		if(isSubsequence(sor))
			return 0;
		else
			return 1;
	}
	if(say[0] - x[0] + x[1] + 1 <= n/2 + 1){
		for(int i = 1; i <= x[1] + 1; i++)
			sor.pb(1);
		for(int i = 1; i <= say[0] - x[0]; i++)
			sor.pb(0);
		// for(int i = 0; i < sor.size(); i++)cout << sor[i] << " ";cout << endl;
		if(isSubsequence(sor))
			return 1;
		else
			return 0;
	}
	return 0;
}

vi findSequence (int N){
		x[0] = x[1] = 0;
	say[0] = say[1] = -1;
	n = N;
	vi ans;
	for(int i = 1; i <= N/2 + 1; i++){
		vi sor(i, 0);
		if(!isSubsequence(sor)){
			say[0] = i - 1;
			break;
		}
	}
	if(say[0] == -1){
		for(int i = 1; i <= N/2 + 1; i++){
			vi sor(i, 1);
			if(!isSubsequence(sor)){
				say[1] = i - 1;
				break;
			}
		}
		say[0] = N - say[1];
	}
	else
		say[1] = N - say[0];
	// cout << say[1] << " " << say[0] << endl;
	int az = 0;
	if(say[1] <= N/2)
		az = 1;
	for(int i = 1; i <= N; i++){
		int xx = sor();
		x[xx]++;
		ans.pb(xx);
	}
// 	vi a, b;
// 	for(int i = 0; i <= say[az]; i++){
// 		vi sor;
// 		for(int j = 1; j <= i; j++)
// 			sor.pb(az);
// 		sor.pb(!az);
// 		for(int j = i + 1; j <= say[az]; j++)
// 			sor.pb(az);
// 		// for(int j = 0; j < sor.size(); j++)cout << sor[j] << " ";cout << endl;
// 		if(isSubsequence(sor)){
// 			a.pb(i);
// 			b.pb(0);
// 		}
// 	}
// 	if(a.back() != say[az]){
// 		a.pb(say[az]);
// 		b.pb(0);
// 	}
// 	int top = 0;
// 	vi yer;
// 	for(int i = 0; i < a.size(); i++){

// 		int kac = - 1;
// 		for(int j = 1; j <= (say[!az] + 1)/2; j++){
// 			vi sor;
// 			for(int k = 1; k <= a[i]; k++)
// 				sor.pb(az);
// 			for(int k = 1; k <= j; k++)
// 				sor.pb(!az);
// 			for(int k = a[i] + 1; k <= say[az]; k++)
// 				sor.pb(az);
// 			if(!isSubsequence(sor)){
// 				kac = j - 1;
// 				break;
// 			}
// 		}
// 		if(kac == -1)
// 			yer.pb(i);
// 		else{
// 			top += kac;
// 			b[i] = kac;
// 		}
// 	}
// 	// for(int i = 0; i < a.size(); i++)cout << a[i] << " ";cout << endl;
// 	// for(int i = 0; i < b.size(); i++)cout << b[i] << " ";cout << endl;
// 	// 	cout << yer[0] << endl;
// 	for(int i = 0; i < a.size(); i++){
// 		int kac = 0;
// 		if(i == 0)
// 			kac = a[0];
// 		else
// 			kac = a[i] - a[i - 1];
// 		for(int j = 1; j <= kac; j++)
// 			ans.pb(az);
// 		if(yer.size() >= 2 and (yer[0] == i or yer[1] == i) )
// 			for(int i = 1; i <= (say[!az] + 1)/2; i++)
// 				ans.pb(!az);
// 		else if(yer.empty() or (yer.size() == 1 and yer[0] != i) )
// 			for(int j = 1; j <= b[i]; j++)
// 				ans.pb(!az);
// 		else if(yer.size() == 1 and yer[0] == i)
// 			for(int i = 1; i <= say[!az] - top; i++)
// 				ans.pb(!az);
// 	}
	return ans;
}
// int main () {
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	srand(time(0));
// 	int tst = 1000;
// 	while(tst--){
// 		int n = 100;
// 		maxQ = 0;
// 		theRealAnswer.clear();
// 		for (int i=1; i<=n; i++)
// 		    theRealAnswer.push_back (rand()%2);

// 		vi ans = findSequence (n);
// 		if (ans.size () != theRealAnswer.size ())
// 		{
// 		    printf ("Different lengths\n");
// 		    for (int i = 0; i < ans.size(); i++)
// 		        printf ("%d ", ans[i]);
// 		    printf ("\n");
// 		    return 0;
// 		}

// 		for (int i=0; i<ans.size (); i++)
// 		    if (ans[i] != theRealAnswer[i])
// 		    {
// 		        printf ("WA position %d\n", i + 1);
// 		        for (int i = 0; i < ans.size(); i++)
// 		            printf ("%d %d\n", theRealAnswer[i], ans[i]);
// 		        printf ("\n");
// 		        return 0;
// 		    }
// 		printf ("Ok, biggest queried length %d\n", maxQ);
// 	}
// return 0;
// }

Compilation message (stderr)

hidden.cpp: In function 'vi findSequence(int)':
hidden.cpp:79:6: warning: variable 'az' set but not used [-Wunused-but-set-variable]
  int az = 0;
      ^~
hidden.cpp: At global scope:
hidden.cpp:9:12: warning: 'maxQ' defined but not used [-Wunused-variable]
 static int maxQ = 0;
            ^~~~
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