oj.uz

Submission #127453

# Submission time Handle Problem Language Result Execution time Memory
127453 2019-07-09T11:42:24 Z E869120 Hidden Sequence (info1cup18_hidden) C++14
64 / 100
 16 ms 6648 KB 
#include <iostream>
#include <vector>
#include "grader.h"
using namespace std;

int sum[109], cnts;
vector<int> G[1 << 18]; bool S[1 << 18];

vector<int> findSequence(int N) {
	if (N <= 10) {
		for (int t = 1; t <= (N / 2) + 1; t++) {
			for (int i = 0; i < (1 << t); i++) {
				for (int j = 0; j < t; j++) G[cnts].push_back((i / (1 << j)) % 2);
				S[cnts] = isSubsequence(G[cnts]); cnts++;
			}
		}
		for (int i = 0; i < (1 << N); i++) {
			vector<int> T;
			for (int j = 0; j < N; j++) T.push_back((i / (1 << j)) % 2);

			bool ans = true;

			for (int j = 0; j < cnts; j++) {
				int ret1 = 0; bool flag = false;
				for (int k = 0; k < N; k++) {
					if (T[k] == G[j][ret1]) ret1++;
					if (ret1 == G[j].size()) break;
				}
				if (ret1 == G[j].size()) flag = true;

				if (flag != S[j]) ans = false;
			}

			if (ans == true) return T;
		}
		return vector<int>{-1};
	}
	else {
		int zero = 0, one = 0;
		for (int i = 1; i <= (N + 1) / 2; i++) {
			vector<int> L0(i, 0); if (isSubsequence(L0) == true) zero++;
			vector<int> L1(i, 1); if (isSubsequence(L1) == true) one++;
		}
		if (zero < one) one = N - zero;
		else zero = N - one;

		if (zero < one) {
			for (int i = 0; i <= zero; i++) {
				for (int j = 1; j <= (one / 2) + 1; j++) {
					vector<int>vec;
					for (int k = 0; k <= zero; k++) {
						if (i == k) {
							for (int l = 0; l < j; l++) vec.push_back(1);
						}
						if (k < zero) vec.push_back(0);
					}
					if (isSubsequence(vec) == true) sum[i] = j;
					else break;
				}
				if (sum[i] == (one / 2) + 1) sum[i] = -1;
			}
			int rem = one;
			for (int i = 0; i <= zero; i++) { if (sum[i] != -1) rem -= sum[i]; }
			for (int i = 0; i <= zero; i++) { if (sum[i] == -1) sum[i] = rem; }

			vector<int>ans;
			for (int i = 0; i <= zero; i++) {
				for (int j = 0; j < sum[i]; j++) ans.push_back(1);
				if (i < zero) ans.push_back(0);
			}
			return ans;
		}
		else {
			for (int i = 0; i <= one; i++) {
				for (int j = 1; j <= (zero / 2) + 1; j++) {
					vector<int>vec;
					for (int k = 0; k <= one; k++) {
						if (i == k) {
							for (int l = 0; l < j; l++) vec.push_back(0);
						}
						if (k < one) vec.push_back(1);
					}
					if (isSubsequence(vec) == true) sum[i] = j;
					else break;
				}
				if (sum[i] == (zero / 2) + 1) sum[i] = -1;
			}
			int rem = zero;
			for (int i = 0; i <= one; i++) { if (sum[i] != -1) rem -= sum[i]; }
			for (int i = 0; i <= one; i++) { if (sum[i] == -1) sum[i] = rem; }

			vector<int>ans;
			for (int i = 0; i <= one; i++) {
				for (int j = 0; j < sum[i]; j++) ans.push_back(0);
				if (i < one) ans.push_back(1);
			}
			return ans;
		}
	}
}

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (ret1 == G[j].size()) break;
          ~~~~~^~~~~~~~~~~~~~
hidden.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ret1 == G[j].size()) flag = true;
         ~~~~~^~~~~~~~~~~~~~
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 7 ms 6476 KB Output is correct: Maximum length of a query = 5
2 Correct 10 ms 6392 KB Output is correct: Maximum length of a query = 6
3 Correct 8 ms 6392 KB Output is correct: Maximum length of a query = 5
4 Correct 9 ms 6520 KB Output is correct: Maximum length of a query = 5
5 Correct 7 ms 6392 KB Output is correct: Maximum length of a query = 4

Subtask #2
44.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 6648 KB Output is partially correct: Maximum length of a query = 86
2 Partially correct 13 ms 6520 KB Output is partially correct: Maximum length of a query = 92
3 Partially correct 15 ms 6568 KB Output is partially correct: Maximum length of a query = 102
4 Partially correct 13 ms 6440 KB Output is partially correct: Maximum length of a query = 87
5 Partially correct 12 ms 6472 KB Output is partially correct: Maximum length of a query = 102
6 Partially correct 16 ms 6392 KB Output is partially correct: Maximum length of a query = 130
7 Partially correct 12 ms 6532 KB Output is partially correct: Maximum length of a query = 144
8 Partially correct 14 ms 6392 KB Output is partially correct: Maximum length of a query = 97
9 Partially correct 13 ms 6392 KB Output is partially correct: Maximum length of a query = 114
10 Partially correct 14 ms 6392 KB Output is partially correct: Maximum length of a query = 125
11 Partially correct 14 ms 6392 KB Output is partially correct: Maximum length of a query = 97
12 Partially correct 15 ms 6520 KB Output is partially correct: Maximum length of a query = 150
13 Partially correct 12 ms 6480 KB Output is partially correct: Maximum length of a query = 106