#include "bits/stdc++.h"
using namespace std;
bool isSubsequence (vector < int > v);
vector<int> findSequence(int N) {
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;
for (int i = 0; i <= cnt[t]; i++) {
if (lens[i] == j - 1) {
bool chk = false;
for (int s = 0; s <= cnt[t] && !chk; s++) {
for (int l = 0; l <= i && !chk; l++) {
int r = s - l;
if (r > cnt[t] - i) continue;
int L = l, R = cnt[t] - r;
// cout << i << " " << l << " " << r << endl;
if (pref[R + 1] - pref[L] == 1) {
// cout << j << " " << i << " " << l << " " << r << endl;
chk = true;
vector<int> qu(l, t);
for (int k = 0; k < j; k++) {
qu.push_back(1 - t);
}
for (int k = 0; k < r; k++) {
qu.push_back(t);
}
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
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:22:20: warning: value computed is not used [-Wunused-value]
22 | cnt[0] - N - cnt[1];
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 |
Partially correct |
1 ms |
336 KB |
Output is partially correct: Maximum length of a query = 8 |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct: Maximum length of a query = 5 |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct: Maximum length of a query = 5 |
| 5 |
Partially correct |
1 ms |
336 KB |
Output is partially correct: Maximum length of a query = 5 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
5 ms |
336 KB |
Output is partially correct: Maximum length of a query = 85 |
| 2 |
Correct |
4 ms |
336 KB |
Output is correct: Maximum length of a query = 90 |
| 3 |
Partially correct |
5 ms |
336 KB |
Output is partially correct: Maximum length of a query = 100 |
| 4 |
Partially correct |
4 ms |
336 KB |
Output is partially correct: Maximum length of a query = 80 |
| 5 |
Partially correct |
5 ms |
460 KB |
Output is partially correct: Maximum length of a query = 101 |
| 6 |
Partially correct |
5 ms |
336 KB |
Output is partially correct: Maximum length of a query = 109 |
| 7 |
Correct |
4 ms |
336 KB |
Output is correct: Maximum length of a query = 97 |
| 8 |
Correct |
4 ms |
504 KB |
Output is correct: Maximum length of a query = 83 |
| 9 |
Partially correct |
8 ms |
336 KB |
Output is partially correct: Maximum length of a query = 126 |
| 10 |
Partially correct |
6 ms |
848 KB |
Output is partially correct: Maximum length of a query = 121 |
| 11 |
Partially correct |
5 ms |
452 KB |
Output is partially correct: Maximum length of a query = 97 |
| 12 |
Incorrect |
6 ms |
592 KB |
Output is not correct: The returned sequence does not match the hidden one |
| 13 |
Halted |
0 ms |
0 KB |
- |
