Submission #127453

#	Time	Username	Problem	Language	Result	Execution time	Memory
127453		E869120	Hidden Sequence (info1cup18_hidden)	C++14	64 / 100	16 ms	6648 KiB

hidden

#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 (stderr)

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 / 20
• Subtask 2: 44 / 80