oj.uz

Submission #102667

# Submission time Handle Problem Language Result Execution time Memory
102667 2019-03-26T15:29:31 Z IOrtroiii Hidden Sequence (info1cup18_hidden) C++14
100 / 100
 163 ms 412 KB 
#include <bits/stdc++.h>
#ifndef F4F
#include "grader.h"
#endif
using namespace std;

int cnt[205];

vector<int> a;

#ifdef F4F
bool isSubsequence(vector<int> nw) {
	int ptr = 0;
	for (int v : a) {
		if (ptr < nw.size() && v == nw[ptr]) {
			++ptr;
		}
	}
	return ptr == nw.size();
}
#endif

vector<int> findSequence(int n) {
	int lim = (n / 2) + 1;
	int num = -1, len = -1;
	for (int t = 0; t < 2; ++t) {
		vector<int> nw;
		for (int i = 1; i <= lim; ++i) {
			nw.push_back(t);
			if (!isSubsequence(nw)) {
				num = t;
				len = i - 1;
				break;
			}
		}
	}
	cnt[len] = n - len;
	for (int i = 0; i < len; ++i) {
		int x = i, y = len - 1 - i;
		int z = 0, t = 0;
		
		while (x + t < lim) {
			vector<int> nw;
			for (int j = 0; j <= x; ++j) nw.push_back(num);
			for (int j = 0; j < t; ++j) nw.push_back(num ^ 1);
			if (!isSubsequence(nw)) {
				break;
			} 
			++t;
		}
		
		while (y + z < lim) {
			vector<int> nw;
			for (int j = 0; j < z; ++j) nw.push_back(num ^ 1);
			for (int j = 0; j <= y; ++j) nw.push_back(num);
			if (!isSubsequence(nw)) {
				break;
			}
			++z;
		}
		
		--z, --t;
		if (x + t <= y + z) {
			cnt[i] = n - len - t;
		} else {
			cnt[i] = z;
		}
	}
	
	for (int i = len; i > 0; --i) cnt[i] -= cnt[i - 1];
	vector<int> ans;
	for (int i = 0; i < len; ++i) {
		for (int j = 0; j < cnt[i]; ++j) ans.push_back(num ^ 1);
		ans.push_back(num); 
	}
	for (int i = 0; i < cnt[len]; ++i) ans.push_back(num ^ 1);
	return ans;
}

#ifdef F4F
int main() {
	int n;
	cin >> n;
	a.resize(n);
	for (int &x : a) cin >> x;
	auto nw = findSequence(n);
	assert(nw == a);
}
#endif

Compilation message

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 3 ms 256 KB Output is correct: Maximum length of a query = 5
2 Correct 3 ms 304 KB Output is correct: Maximum length of a query = 6
3 Correct 2 ms 256 KB Output is correct: Maximum length of a query = 5
4 Correct 2 ms 384 KB Output is correct: Maximum length of a query = 5
5 Correct 3 ms 384 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 384 KB Output is correct: Maximum length of a query = 83
2 Correct 93 ms 384 KB Output is correct: Maximum length of a query = 90
3 Correct 137 ms 384 KB Output is correct: Maximum length of a query = 96
4 Correct 65 ms 256 KB Output is correct: Maximum length of a query = 77
5 Correct 126 ms 284 KB Output is correct: Maximum length of a query = 95
6 Correct 76 ms 384 KB Output is correct: Maximum length of a query = 87
7 Correct 114 ms 384 KB Output is correct: Maximum length of a query = 97
8 Correct 62 ms 412 KB Output is correct: Maximum length of a query = 83
9 Correct 108 ms 256 KB Output is correct: Maximum length of a query = 101
10 Correct 151 ms 256 KB Output is correct: Maximum length of a query = 100
11 Correct 161 ms 384 KB Output is correct: Maximum length of a query = 96
12 Correct 130 ms 384 KB Output is correct: Maximum length of a query = 100
13 Correct 163 ms 384 KB Output is correct: Maximum length of a query = 101