Submission #882748

#	Time	Username	Problem	Language	Result	Execution time	Memory
882748		rainboy	Hidden Sequence (info1cup18_hidden)	C++17	100 / 100	4 ms	940 KiB

hidden

#include "grader.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

vi findSequence(int n) {
	int c, k;
	for (k = 0; k <= n / 2; k++)
		for (c = 0; c < 2; c++)
			if (!isSubsequence(vi(k + 1, c)))
				goto out;
out:
	vi ll(k + 1, 0);
	int sum = 0;
	for (int l = 0; l <= n / 2; l++) {
		if (sum == n - k)
			break;
		int h_ = -1;
		for (int h = 0; h <= k; h++)
			if (ll[h] == l) {
				if (h_ == -1)
					h_ = h;
				else {
					h_ = -1;
					break;
				}
			}
		if (h_ != -1) {
			ll[h_] += n - k - sum;
			break;
		}
		for (int h = 0; h <= k; h++)
			if (ll[h] == l) {
				vi aa, bb;
				if (l == 0) {
					for (int h_ = 0; h_ < h; h_++)
						aa.push_back(c);
					aa.push_back(c ^ 1);
					for (int h_ = h; h_ < k; h_++)
						aa.push_back(c);
				} else {
					for (int h_ = 0, c_ = 0; h_ < h; )
						if (ll[h_++] == c_) {
							while (h_ < h && ll[h_] == 0)
								h_++;
							if (h_ < h)
								aa.push_back(c ^ 1), c_ = l == 1 ? 0 : 1;
						} else
							aa.push_back(c), c_ = 0;
					for (int g = 0; g <= l; g++)
						aa.push_back(c ^ 1);
					for (int h_ = k, c_ = 0; h_ > h; )
						if (ll[h_--] == c_) {
							while (h_ > h && ll[h_] == 0)
								h_--;
							if (h_ > h)
								bb.push_back(c ^ 1), c_ = l == 1 ? 0 : 1;
						} else
							bb.push_back(c), c_ = 0;
					int m = bb.size();
					for (int h = m - 1; h >= 0; h--)
						aa.push_back(bb[h]);
				}
				if (isSubsequence(aa))
					ll[h]++, sum++;
			}
	}
	vi aa;
	for (int h = 0; h <= k; h++) {
		for (int g = 0; g < ll[h]; g++)
			aa.push_back(c ^ 1);
		if (h < k)
			aa.push_back(c);
	}
	return aa;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:28:26: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   28 |     fprintf (fifo_out, "%d\n", ans.size ());
      |                         ~^     ~~~~~~~~~~~
      |                          |              |
      |                          int            std::vector<int>::size_type {aka long unsigned int}
      |                         %ld
grader.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0; i<ans.size () && i < N; i++)
      |                   ~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80