Submission #67085

#	Time	Username	Problem	Language	Result	Execution time	Memory
67085		ekrem	Hidden Sequence (info1cup18_hidden)	C++11	59 / 100	11 ms	556 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;
// }

vi findSequence (int N){
	vi ans;
	int say[2] = {-1, -1};
	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];
	int az = 0;
	if(say[1] <= N/2)
		az = 1;
	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 = 10000;
// while(tst--){
// int n = 10;
// 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:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
hidden.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
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: 15 / 20
• Subtask 2: 44 / 80