Submission #102667

#	Time	Username	Problem	Language	Result	Execution time	Memory
102667		IOrtroiii	Hidden Sequence (info1cup18_hidden)	C++14	100 / 100	163 ms	412 KiB

hidden

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

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: 80 / 80