#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);
for (int i = 0; i <= cnt[t]; i++) {
for (int j = 1; j + cnt[t] <= mx; j++) {
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;
} else {
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 |
Incorrect |
1 ms |
336 KB |
Output is not correct: The returned sequence does not match the hidden one |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
508 KB |
Output is not correct: The returned sequence does not match the hidden one |
| 2 |
Halted |
0 ms |
0 KB |
- |
