// M
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
vector < int > findSequence(int n)
{
// Figuring out the lesser of the two
int w;
int MXlen = n / 2 + 1;
vector < int > S(MXlen, 0);
if (isSubsequence(S))
w = 1;
else
w = 0;
// Now to find the number of ws
int k = n / 2;
while (k && !isSubsequence(vector < int > (k, w)))
k --;
if (!k)
return vector < int > (n, !w);
// Next up, identifying non-empty sections
vector < int > A(k + 1, 0);
for (int i = 0; i <= k; i ++)
{
S = vector < int > (k + 1, w);
S[i] = !w;
if (isSubsequence(S))
A[i] = 1;
}
/*printf("%d ::\n", k);
for (int i = 0; i <= k; i ++)
printf("%d ", A[i]);
printf("\n");*/
MXlen = n / 2 + 3;
// Now to find the size of smaller sections
vector < int > SZ(k + 1, 0);
vector < int > F(k + 1, 0);
for (int i = 0; i <= k; i ++)
if (A[i]) F[i] = 1;
for (int __ = 1; __ <= n; __ ++)
for (int i = 0; i <= k; i ++)
if (A[i] && F[i] == 1)
{
S = {};
for (int j = 0; j < i; j ++)
{
if (A[j])
S.push_back(w);
else if (A[j + 1])
S.push_back(!w);
}
if (S.size() && S.back() == !w)
S.pop_back();
vector < int > S2;
for (int j = k; j > i; j --)
{
if (A[j])
S2.push_back(w);
else if (A[j - 1] && j - 1 > i)
S2.push_back(!w);
}
reverse(S2.begin(), S2.end());
int ff = 0;
for (int j = i + 1; j <= k; j ++)
ff |= A[j];
if (!ff) S2 = {};
for (int h = 0, sm = SZ[h]; h > i; h --)
{
if (F[h]) break;
if (h - 1 > i)
{
sm += SZ[h - 1];
if (F[h - 1])
break;
}
vector < int > Tmp(sm, !w);
for (int j = h - 1; j > i; j --)
{
if (A[j])
Tmp.push_back(w);
else if (A[j - 1] && j - 1 > i)
Tmp.push_back(!w);
}
reverse(Tmp.begin(), Tmp.end());
if (Tmp.size() < S2.size())
S2.swap(Tmp);
}
/*printf("%d =======================\n", i);
printf("%d :: ", i);
for (int a : S)
printf("%d ", a);
printf(":::: ");
for (int a : S2)
printf("%d ", a);
printf("\n");*/
int sz = 1;
bool Fail = 0;
while ((int)S.size() + (int)S2.size() + sz + 1 <= MXlen)
{
sz ++;
vector < int > T = S;
for (int j = 0; j < sz; j ++)
T.push_back(!w);
for (int a : S2)
T.push_back(a);
if (!isSubsequence(T))
{Fail = 1; sz --; break;}
}
SZ[i] = sz;
if (!Fail)
F[i] = 1;
else
F[i] = 0;
//printf("%d :: %d :: %d\n", SZ[i], (int)Fail, F[i]);
}
/*for (int i = 0; i <= k; i ++)
printf("(%d %d) ", SZ[i], F[i]);
printf("\n");*/
int SM = k, cc = 0;
for (int i = 0; i <= k; i ++)
if (!F[i])
SM += SZ[i];
else
cc ++;
if (cc <= 1)
for (int i = 0; i <= k; i ++)
if (F[i])
SZ[i] = n - SM;
vector < int > Res;
for (int i = 0; i <= k; i ++)
{
for (int j = 0; j < SZ[i]; j ++)
Res.push_back(!w);
if (i < k)
Res.push_back(w);
}
return Res;
}
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
fprintf (fifo_out, "%d\n", ans.size ());
~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<ans.size () && i < N; i++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
256 KB |
Output is partially correct: Maximum length of a query = 6 |
| 2 |
Partially correct |
1 ms |
256 KB |
Output is partially correct: Maximum length of a query = 7 |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct: Maximum length of a query = 5 |
| 4 |
Partially correct |
1 ms |
256 KB |
Output is partially correct: Maximum length of a query = 6 |
| 5 |
Partially correct |
0 ms |
256 KB |
Output is partially correct: Maximum length of a query = 5 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct: Maximum length of a query = 83 |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct: Maximum length of a query = 90 |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct: Maximum length of a query = 96 |
| 4 |
Correct |
4 ms |
256 KB |
Output is correct: Maximum length of a query = 77 |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct: Maximum length of a query = 95 |
| 6 |
Correct |
4 ms |
256 KB |
Output is correct: Maximum length of a query = 87 |
| 7 |
Correct |
5 ms |
256 KB |
Output is correct: Maximum length of a query = 97 |
| 8 |
Correct |
3 ms |
256 KB |
Output is correct: Maximum length of a query = 83 |
| 9 |
Correct |
4 ms |
256 KB |
Output is correct: Maximum length of a query = 101 |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct: Maximum length of a query = 100 |
| 11 |
Partially correct |
4 ms |
256 KB |
Output is partially correct: Maximum length of a query = 97 |
| 12 |
Correct |
3 ms |
256 KB |
Output is correct: Maximum length of a query = 100 |
| 13 |
Correct |
3 ms |
372 KB |
Output is correct: Maximum length of a query = 101 |
