oj.uz

Submission #127430

# Submission time Handle Problem Language Result Execution time Memory
127430 2019-07-09T11:18:20 Z E869120 Hidden Sequence (info1cup18_hidden) C++14
15 / 100
 154 ms 376 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include "grader.h"
using namespace std;

int sum[109];

vector<int> findSequence (int N) {
	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;

	int mask = 0;

	if (zero > one) {
		swap(zero, one);
		mask ^= 1;
	}

	for (int i = 0; i <= zero; i++) sum[i] = -1;

	int LIMITLENGTH = (N / 2) + 3;

	for (int level = 1; level <= (one / 2) + 1; level++) {
		for (int j = 0; j <= zero; j++) {
			if (sum[j] != -1) continue;

			vector<int> cl, cr;
			for (int k = 0; k < j; k++) {
				int P = level - 1; if (sum[k] != -1) P = sum[k];
				for (int l = 0; l < P; l++) cl.push_back(1 ^ mask);
				cl.push_back(0 ^ mask);
			}
			for (int k = j; k < zero; k++) {
				cr.push_back(0 ^ mask);
				int P = level - 1; if (sum[k + 1] != -1) P = sum[k + 1];
				for (int l = 0; l < P; l++) cr.push_back(1 ^ mask);
			}

			for (int t = 0; t < 20; t++) {
				vector<bool>E1(cl.size(), false);
				vector<bool>E2(cr.size(), false);

				int KOSUU = min((int)cl.size() + (int)cr.size(), LIMITLENGTH - level);
				while (true) {
					for (int k = 0; k < E1.size(); k++) E1[k] = false;
					for (int k = 0; k < E2.size(); k++) E2[k] = false;

					int cnt = 0;
					for (int k = 0; k < E1.size(); k++) { if (rand() % (cl.size() + cr.size()) < KOSUU) { E1[k] = true; cnt++; } }
					for (int k = 0; k < E2.size(); k++) { if (rand() % (cl.size() + cr.size()) < KOSUU) { E2[k] = true; cnt++; } }
					if (cnt == KOSUU) break;
				}

				vector<int>B;
				for (int k = 0; k < E1.size(); k++) { if (E1[k] == true) B.push_back(cl[k]); }
				for (int k = 0; k < level; k++) B.push_back(1 ^ mask);
				for (int k = 0; k < E2.size(); k++) { if (E2[k] == true) B.push_back(cr[k]); }

				bool I = isSubsequence(B);
				if (I == false) { sum[j] = level - 1; break; }
			}
		}
	}

	int ret = one; for (int i = 0; i <= zero; i++) { if (sum[i] != -1) ret -= sum[i]; }
	for (int i = 0; i <= zero; i++) {
		if (sum[i] == -1) sum[i] = ret;
	}

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

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:51:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < E1.size(); k++) E1[k] = false;
                      ~~^~~~~~~~~~~
hidden.cpp:52:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < E2.size(); k++) E2[k] = false;
                      ~~^~~~~~~~~~~
hidden.cpp:55:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < E1.size(); k++) { if (rand() % (cl.size() + cr.size()) < KOSUU) { E1[k] = true; cnt++; } }
                      ~~^~~~~~~~~~~
hidden.cpp:55:81: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < E1.size(); k++) { if (rand() % (cl.size() + cr.size()) < KOSUU) { E1[k] = true; cnt++; } }
                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
hidden.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < E2.size(); k++) { if (rand() % (cl.size() + cr.size()) < KOSUU) { E2[k] = true; cnt++; } }
                      ~~^~~~~~~~~~~
hidden.cpp:56:81: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < E2.size(); k++) { if (rand() % (cl.size() + cr.size()) < KOSUU) { E2[k] = true; cnt++; } }
                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
hidden.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < E1.size(); k++) { if (E1[k] == true) B.push_back(cl[k]); }
                     ~~^~~~~~~~~~~
hidden.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < E2.size(); k++) { if (E2[k] == true) B.push_back(cr[k]); }
                     ~~^~~~~~~~~~~
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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 376 KB Output is partially correct: Maximum length of a query = 7
2 Partially correct 3 ms 248 KB Output is partially correct: Maximum length of a query = 8
3 Partially correct 3 ms 248 KB Output is partially correct: Maximum length of a query = 7
4 Partially correct 3 ms 248 KB Output is partially correct: Maximum length of a query = 7
5 Partially correct 3 ms 248 KB Output is partially correct: Maximum length of a query = 6

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 316 KB Output is not correct: The length of the returned sequence is not N
2 Halted 0 ms 0 KB -