oj.uz

Submission #44829

# Submission time Handle Problem Language Result Execution time Memory
44829 2018-04-07T13:14:17 Z cheater2k Hidden Sequence (info1cup18_hidden) C++17
100 / 100
 152 ms 544 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int N = 225;

int num = 0;
int len = 0;
int n;
int t[N];

vector <int> findSequence(int _n) {
	n = _n;
	for (int k = 0; k < 2; ++k) {
		for (int i = 1; i <= (n / 2) + 1; ++i) {
			vector <int> vec;
			for (int j = 1; j <= i; ++j) vec.push_back(k);
			if (!isSubsequence(vec)) {
				num = k;
				len = i - 1;
				break;
			}
		}
	}

	if (!len) {
		vector <int> vec;
		for (int i = 1; i <= n; ++i) vec.push_back(num ^ 1);
		return vec;
	}

	for (int i = 1; i <= len; ++i) {
		// find the number of {num ^ 1} before the i-th {num}
		bool flag0, flag1;
		int lef0 = i - 1;
		int rig0 = len - i;

		int l = 0, r = 0;

		vector <int> vec;
		for (int j = 1; j <= (n / 2) - rig0; ++j) {
			// num ^ 1 (j times), num, num (rig0 times) 
			vec.clear();
			for (int k = 1; k <= j; ++k) vec.push_back(num ^ 1);
			vec.push_back(num);
			for (int k = 1; k <= rig0; ++k) vec.push_back(num);
			flag0 = isSubsequence(vec);
			if (flag0) ++l;
			else break;
		}

		for (int j = 1; j <= (n / 2) - lef0; ++j) {
			// num (lef0 times), num, num ^ 1 (j times)
			vec.clear();
			for (int k = 1; k <= lef0; ++k) vec.push_back(num);
			vec.push_back(num);
			for (int k = 1; k <= j; ++k) vec.push_back(num ^ 1);
			flag1 = isSubsequence(vec);
			if (flag1) ++r;
			else break;
		}

		if (!flag1) t[i] = n - len - r;
		else t[i] = l; 
	}

	vector <int> res;
	for (int i = 1; i <= len; ++i) {
		int add = t[i] - t[i - 1];
		while(add--) res.push_back(num ^ 1);
		res.push_back(num);
	}

	int add = n - len - t[len];
	while(add--) res.push_back(num ^ 1);

	return res;
}

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:64:3: warning: 'flag1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (!flag1) t[i] = n - len - r;
   ^~
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 248 KB Output is correct: Maximum length of a query = 5
2 Correct 2 ms 308 KB Output is correct: Maximum length of a query = 6
3 Correct 2 ms 472 KB Output is correct: Maximum length of a query = 5
4 Correct 2 ms 472 KB Output is correct: Maximum length of a query = 5
5 Correct 2 ms 496 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 496 KB Output is correct: Maximum length of a query = 83
2 Correct 101 ms 516 KB Output is correct: Maximum length of a query = 90
3 Correct 122 ms 516 KB Output is correct: Maximum length of a query = 96
4 Correct 78 ms 532 KB Output is correct: Maximum length of a query = 77
5 Correct 133 ms 532 KB Output is correct: Maximum length of a query = 95
6 Correct 73 ms 532 KB Output is correct: Maximum length of a query = 87
7 Correct 109 ms 532 KB Output is correct: Maximum length of a query = 97
8 Correct 81 ms 532 KB Output is correct: Maximum length of a query = 83
9 Correct 152 ms 532 KB Output is correct: Maximum length of a query = 101
10 Correct 132 ms 532 KB Output is correct: Maximum length of a query = 100
11 Correct 127 ms 544 KB Output is correct: Maximum length of a query = 96
12 Correct 116 ms 544 KB Output is correct: Maximum length of a query = 100
13 Correct 134 ms 544 KB Output is correct: Maximum length of a query = 101