#include "bits/stdc++.h"
using namespace std;
bool isSubsequence (vector < int > v);
vector<int> findSequence(int N) {
mt19937 gen(22);
int mx = N / 2 + 1;
vector<int> cnt(2);
for (int t = 0; t < 2; t++) {
for (int i = 1; i <= mx; i++) {
vector<int> qu(i, t);
if (isSubsequence(qu)) {
cnt[t] = i;
} else {
break;
}
}
}
int t = 0;
if (cnt[0] > cnt[1]) {
cnt[0] = N - cnt[1];
t = 1;
} else {
cnt[1] = N - cnt[0];
t = 0;
}
vector<int> lens(cnt[t] + 1), pref;
for (int j = 1; j <= mx; j++) {
int good = 0;
pref.resize(lens.size() + 1);
for (int i = 1; i < (int) pref.size(); i++) {
pref[i] = pref[i - 1] + int(lens[i - 1] != 0 || j == 1);
}
// for (auto& x : pref) cout << x << " + " ; cout << endl;
vector<int> ord(cnt[t] + 1);
std::iota(ord.begin(), ord.end(), 0);
std::shuffle(ord.begin(), ord.end(), gen);
for (auto i : ord) {
if (std::accumulate(lens.begin(), lens.end(), 0) == cnt[1 - t]) {
break;
}
if (lens[i] == j - 1) {
if (j == 1) {
vector<int> qu(i, t);
for (int k = 0; k < j; k++) {
qu.push_back(1 - t);
}
for (int k = 0; k < cnt[t] - i; k++) {
qu.push_back(t);
}
if (isSubsequence(qu)) {
lens[i] = j;
good++;
}
} else {
vector<int> qu, qu2;
int cur = 0;
while (cur < i) {
if (lens[cur] > 0) {
qu.push_back(t);
cur++;
} else {
while (cur < i && lens[cur] == 0) {
cur++;
}
if (cur < i) {
qu.push_back(1 - t);
}
}
}
for (int k = 0; k < j; k++) {
qu.push_back(1 - t);
}
cur = cnt[t];
while (cur > i) {
if (lens[cur] > 0) {
qu2.push_back(t);
cur--;
} else {
while (cur > i && lens[cur] == 0) {
cur--;
}
if (cur > i) {
qu2.push_back(1 - t);
}
}
}
while (!qu2.empty()) {
qu.push_back(qu2.back());
qu2.pop_back();
}
if (isSubsequence(qu)) {
lens[i] = j;
good++;
}
}
}
}
if (good <= 1) {
break;
}
}
int pos = std::max_element(lens.begin(), lens.end()) - lens.begin();
int S = std::accumulate(lens.begin(), lens.end(), 0);
lens[pos] = N - (cnt[t] + (S - lens[pos]));
vector<int> answer(lens[0], 1 - t);
for (int i = 1; i <= cnt[t]; i++) {
answer.push_back(t);
for (int j = 0; j < lens[i]; j++) {
answer.push_back(1 - t);
}
}
return answer;
}
//static int maxQ = 0;
//static vector < int > theRealAnswer;
//
//bool isSubsequence (vector < int > v)
//{
// if (v.size () > maxQ)
// maxQ = v.size ();
// int i = 0;
// for (auto it : v)
// {
// while (i < theRealAnswer.size () && it != theRealAnswer[i]) i ++;
// if (i == theRealAnswer.size ()) return 0;
// i ++;
// }
// return 1;
//}
//
//int main ()
//{
// int n, x;
// scanf ("%d", &n), maxQ = 0;
// for (int i=1; i<=n; i++)
// scanf ("%d", &x), theRealAnswer.push_back (x);
//
// vector < int > ans = findSequence (n);
// if (ans.size () != theRealAnswer.size ())
// {
// printf ("Different lengths\n");
// for (auto it : ans)
// printf ("%d ", it);
// printf ("\n");
// return 0;
// }
//
// for (int i=0; i<ans.size (); i++)
// if (ans[i] != theRealAnswer[i])
// {
// printf ("WA position %d\n", i + 1);
// for (auto it : ans)
// printf ("%d ", it);
// printf ("\n");
// return 0;
// }
// printf ("Ok, biggest queried length %d\n", maxQ);
// return 0;
//}
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++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct: Maximum length of a query = 5 |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct: Maximum length of a query = 6 |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct: Maximum length of a query = 5 |
| 4 |
Correct |
1 ms |
504 KB |
Output is correct: Maximum length of a query = 5 |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct: Maximum length of a query = 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
592 KB |
Output is correct: Maximum length of a query = 83 |
| 2 |
Correct |
4 ms |
456 KB |
Output is correct: Maximum length of a query = 90 |
| 3 |
Correct |
5 ms |
336 KB |
Output is correct: Maximum length of a query = 96 |
| 4 |
Correct |
3 ms |
336 KB |
Output is correct: Maximum length of a query = 77 |
| 5 |
Correct |
6 ms |
336 KB |
Output is correct: Maximum length of a query = 95 |
| 6 |
Correct |
4 ms |
336 KB |
Output is correct: Maximum length of a query = 87 |
| 7 |
Correct |
4 ms |
336 KB |
Output is correct: Maximum length of a query = 97 |
| 8 |
Correct |
3 ms |
336 KB |
Output is correct: Maximum length of a query = 83 |
| 9 |
Correct |
5 ms |
336 KB |
Output is correct: Maximum length of a query = 101 |
| 10 |
Correct |
5 ms |
336 KB |
Output is correct: Maximum length of a query = 100 |
| 11 |
Correct |
3 ms |
336 KB |
Output is correct: Maximum length of a query = 96 |
| 12 |
Correct |
5 ms |
336 KB |
Output is correct: Maximum length of a query = 100 |
| 13 |
Correct |
6 ms |
592 KB |
Output is correct: Maximum length of a query = 101 |
