oj.uz

Submission #882748

# Submission time Handle Problem Language Result Execution time Memory
882748 2023-12-03T15:46:23 Z rainboy Hidden Sequence (info1cup18_hidden) C++17
100 / 100
 4 ms 940 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct: Maximum length of a query = 5
2 Correct 1 ms 344 KB Output is correct: Maximum length of a query = 6
3 Correct 0 ms 344 KB Output is correct: Maximum length of a query = 5
4 Correct 0 ms 344 KB Output is correct: Maximum length of a query = 5
5 Correct 1 ms 344 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 696 KB Output is correct: Maximum length of a query = 80
2 Correct 3 ms 436 KB Output is correct: Maximum length of a query = 84
3 Correct 3 ms 692 KB Output is correct: Maximum length of a query = 96
4 Correct 3 ms 432 KB Output is correct: Maximum length of a query = 77
5 Correct 4 ms 696 KB Output is correct: Maximum length of a query = 95
6 Correct 3 ms 688 KB Output is correct: Maximum length of a query = 87
7 Correct 4 ms 692 KB Output is correct: Maximum length of a query = 96
8 Correct 2 ms 940 KB Output is correct: Maximum length of a query = 83
9 Correct 4 ms 440 KB Output is correct: Maximum length of a query = 101
10 Correct 4 ms 436 KB Output is correct: Maximum length of a query = 100
11 Correct 3 ms 692 KB Output is correct: Maximum length of a query = 96
12 Correct 4 ms 432 KB Output is correct: Maximum length of a query = 100
13 Correct 4 ms 436 KB Output is correct: Maximum length of a query = 101