Submission #47218

#	Time	Username	Problem	Language	Result	Execution time	Memory
47218		Kmcode	Hidden Sequence (info1cup18_hidden)	C++14	100 / 100	8 ms	608 KiB

hidden

#include "bits/stdc++.h"
#include "grader.h"
using namespace std;


int dp[202];
int pr[202];

vector<int> ask(vector<pair<int, int> > v1, vector<int> fin) {
	for (int i = 0; i <= v1.size(); i++) {
		dp[i] = INT_MAX;
		pr[i] = -1;
	}
	dp[0] = 0;
	dp[1] = 0;
	for (int i = 0; i < v1.size(); i++) {
		if (fin[i]) {
			int tmp = v1[i].second;
			dp[i + 2] = min(dp[i + 2], dp[i] + v1[i].second);
			if (dp[i + 2] == dp[i] + v1[i].second) {
				pr[i + 2] = 2;
			}
			v1[i].second = tmp;
		}
		dp[i + 1] = min(dp[i + 1], dp[i] + 1);
		if (dp[i + 1] == dp[i] + 1) {
			pr[i + 1] = 1;
		}
	}
	vector<int> ret;
	int cur = v1.size();
	while (cur>1) {
		if (pr[cur] == 1) {
			ret.push_back(v1[cur - 1].first);
		}
		else {
			while (v1[cur - 2].second--) {
				ret.push_back(v1[cur - 2].first);
			}
		}
		cur -= pr[cur];
	}
	reverse(ret.begin(), ret.end());
	return ret;
}
vector<int> calc(vector<int> v, int add, int lim, int n) {
	int z = 0;
	vector<pair<int, int> > ar;  //kind len
	vector<bool> fin;
	int rest_add = n - v.size();
	for (int i = v.size(); i >= 0; i--) {
		vector<int> tmp = v;
		tmp.insert(tmp.begin() + v.size() - i, add);
		if (isSubsequence(tmp)) {
			if (z) {
				ar.push_back(make_pair(add ^ true, z));
				fin.push_back(true);
				z = 0;
			}
			ar.push_back(make_pair(add, 1));
			fin.push_back(false);
			rest_add--;
			if (i != 0)z++;
		}
		else {
			if (i != 0)z++;
		}
	}
	if (z) {
		ar.push_back(make_pair(add ^ true, z));
		fin.push_back(true);
	}
	int idx = 0;
	while (rest_add) {
		int fc = 0;
		int las = 0;
		for (int i = 0; i < ar.size(); i++) {
			if (fin[i] == false) {
				fc++;
				las = i;
			}
		}

		if (fc == 1) {
			ar[las].second += rest_add;
			rest_add = 0;
			continue;
		}
		if (fin[idx] == false) {
			vector<int> query;
			{
				vector<pair<int, int> > v2;
				vector<int> f2;
				for (int i = 0; i < idx; i++) {
					v2.push_back(ar[i]);
					f2.push_back(fin[i]);
				}
				query = ask(v2, f2);
			}
			int add = ar[idx].second;
			add++;
			while (add--) {
				query.push_back(ar[idx].first);
			}
			{
				vector<pair<int, int> > v2;
				vector<int> f2;
				for (int i = ar.size() - 1; i > idx; i--) {
					v2.push_back(ar[i]);
					f2.push_back(fin[i]);
				}
				auto query2 = ask(v2, f2);
				reverse(query2.begin(), query2.end());
				for (int el : query2) {
					query.push_back(el);
				}
			}
			if (query.size() > (n / 2) + 1) {
				
			}
			else {
				if (isSubsequence(query)) {
					rest_add--;
					ar[idx].second++;
				}
				else {
					fin[idx] = true;
				}
			}
		}
		idx++;
		idx %= ar.size();
	}
	vector<int> ans;
	for (int i = 0; i < ar.size(); i++) {
		while (ar[i].second--) {
			ans.push_back(ar[i].first);
		}
	}
	return ans;
}
vector<int> findSequence(int N) {
	vector<int> zero;
	vector<int> one;
	for (int i = 0; i < N / 2 + 1; i++) {
		zero.push_back(0);
		one.push_back(1);
		if (isSubsequence(zero)) {

		}
		else {
			zero.pop_back();
		}
		if (!isSubsequence(one)) {
			one.pop_back();
		}
	}
	while (zero.size() + one.size() < N) {
		if (zero.size() > one.size()) {
			zero.push_back(0);
		}
		else {
			one.push_back(1);
		}
	}
	if (one.size() > zero.size()) {
		return calc(zero, 1, (N) / 2 + 3, N);
	}
	else {
		return calc(one, 0, (N) / 2 + 3, N);
	}
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> ask(std::vector<std::pair<int, int> >, std::vector<int>)':
hidden.cpp:10:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= v1.size(); i++) {
                  ~~^~~~~~~~~~~~
hidden.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v1.size(); i++) {
                  ~~^~~~~~~~~~~
hidden.cpp: In function 'std::vector<int> calc(std::vector<int>, int, int, int)':
hidden.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ar.size(); i++) {
                   ~~^~~~~~~~~~~
hidden.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (query.size() > (n / 2) + 1) {
        ~~~~~~~~~~~~~^~~~~~~~~~~~~
hidden.cpp:135:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ar.size(); i++) {
                  ~~^~~~~~~~~~~
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:158:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (zero.size() + one.size() < N) {
         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
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