#include <bits/stdc++.h>
#include "grader.h"
#define pb push_back
using namespace std;
typedef vector < int > vi;
static int maxQ = 0;
static vi theRealAnswer;
// bool isSubsequence (vi v){
// if (v.size () > maxQ)
// maxQ = v.size ();
// int i = 0;
// for (int j = 0; j < v.size(); j++){
// while (i < theRealAnswer.size () && v[j] != theRealAnswer[i]) i ++;
// if (i == theRealAnswer.size ()) return 0;
// i++;
// }
// return 1;
// }
int say[2] = {-1, -1}, x[2] = {0, 0}, n;
int sor(){
vi sor;
if(say[1] - x[1] + x[0] + 1 <= n/2 + 1){
for(int i = 1; i <= x[0] + 1; i++)
sor.pb(0);
for(int i = 1; i <= say[1] - x[1]; i++)
sor.pb(1);
// for(int i = 0; i < sor.size(); i++)cout << sor[i] << " ,";cout << endl;
if(isSubsequence(sor))
return 0;
else
return 1;
}
if(say[0] - x[0] + x[1] + 1 <= n/2 + 1){
for(int i = 1; i <= x[1] + 1; i++)
sor.pb(1);
for(int i = 1; i <= say[0] - x[0]; i++)
sor.pb(0);
// for(int i = 0; i < sor.size(); i++)cout << sor[i] << " ";cout << endl;
if(isSubsequence(sor))
return 1;
else
return 0;
}
return 0;
}
vi findSequence (int N){
x[0] = x[1] = 0;
say[0] = say[1] = -1;
n = N;
vi ans;
for(int i = 1; i <= N/2 + 1; i++){
vi sor(i, 0);
if(!isSubsequence(sor)){
say[0] = i - 1;
break;
}
}
if(say[0] == -1){
for(int i = 1; i <= N/2 + 1; i++){
vi sor(i, 1);
if(!isSubsequence(sor)){
say[1] = i - 1;
break;
}
}
say[0] = N - say[1];
}
else
say[1] = N - say[0];
// cout << say[1] << " " << say[0] << endl;
int az = 0;
if(say[1] <= N/2)
az = 1;
for(int i = 1; i <= N; i++){
int xx = sor();
x[xx]++;
ans.pb(xx);
}
// vi a, b;
// for(int i = 0; i <= say[az]; i++){
// vi sor;
// for(int j = 1; j <= i; j++)
// sor.pb(az);
// sor.pb(!az);
// for(int j = i + 1; j <= say[az]; j++)
// sor.pb(az);
// // for(int j = 0; j < sor.size(); j++)cout << sor[j] << " ";cout << endl;
// if(isSubsequence(sor)){
// a.pb(i);
// b.pb(0);
// }
// }
// if(a.back() != say[az]){
// a.pb(say[az]);
// b.pb(0);
// }
// int top = 0;
// vi yer;
// for(int i = 0; i < a.size(); i++){
// int kac = - 1;
// for(int j = 1; j <= (say[!az] + 1)/2; j++){
// vi sor;
// for(int k = 1; k <= a[i]; k++)
// sor.pb(az);
// for(int k = 1; k <= j; k++)
// sor.pb(!az);
// for(int k = a[i] + 1; k <= say[az]; k++)
// sor.pb(az);
// if(!isSubsequence(sor)){
// kac = j - 1;
// break;
// }
// }
// if(kac == -1)
// yer.pb(i);
// else{
// top += kac;
// b[i] = kac;
// }
// }
// // for(int i = 0; i < a.size(); i++)cout << a[i] << " ";cout << endl;
// // for(int i = 0; i < b.size(); i++)cout << b[i] << " ";cout << endl;
// // cout << yer[0] << endl;
// for(int i = 0; i < a.size(); i++){
// int kac = 0;
// if(i == 0)
// kac = a[0];
// else
// kac = a[i] - a[i - 1];
// for(int j = 1; j <= kac; j++)
// ans.pb(az);
// if(yer.size() >= 2 and (yer[0] == i or yer[1] == i) )
// for(int i = 1; i <= (say[!az] + 1)/2; i++)
// ans.pb(!az);
// else if(yer.empty() or (yer.size() == 1 and yer[0] != i) )
// for(int j = 1; j <= b[i]; j++)
// ans.pb(!az);
// else if(yer.size() == 1 and yer[0] == i)
// for(int i = 1; i <= say[!az] - top; i++)
// ans.pb(!az);
// }
return ans;
}
// int main () {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// srand(time(0));
// int tst = 1000;
// while(tst--){
// int n = 100;
// maxQ = 0;
// theRealAnswer.clear();
// for (int i=1; i<=n; i++)
// theRealAnswer.push_back (rand()%2);
// vi ans = findSequence (n);
// if (ans.size () != theRealAnswer.size ())
// {
// printf ("Different lengths\n");
// for (int i = 0; i < ans.size(); i++)
// printf ("%d ", ans[i]);
// 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 (int i = 0; i < ans.size(); i++)
// printf ("%d %d\n", theRealAnswer[i], ans[i]);
// printf ("\n");
// return 0;
// }
// printf ("Ok, biggest queried length %d\n", maxQ);
// }
// return 0;
// }
Compilation message
hidden.cpp: In function 'vi findSequence(int)':
hidden.cpp:79:6: warning: variable 'az' set but not used [-Wunused-but-set-variable]
int az = 0;
^~
hidden.cpp: At global scope:
hidden.cpp:9:12: warning: 'maxQ' defined but not used [-Wunused-variable]
static int maxQ = 0;
^~~~
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 |
Correct |
2 ms |
248 KB |
Output is correct: Maximum length of a query = 5 |
| 2 |
Correct |
4 ms |
436 KB |
Output is correct: Maximum length of a query = 6 |
| 3 |
Correct |
3 ms |
436 KB |
Output is correct: Maximum length of a query = 5 |
| 4 |
Correct |
2 ms |
440 KB |
Output is correct: Maximum length of a query = 5 |
| 5 |
Correct |
2 ms |
440 KB |
Output is correct: Maximum length of a query = 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
464 KB |
Output is correct: Maximum length of a query = 83 |
| 2 |
Correct |
10 ms |
476 KB |
Output is correct: Maximum length of a query = 90 |
| 3 |
Correct |
8 ms |
476 KB |
Output is correct: Maximum length of a query = 96 |
| 4 |
Correct |
6 ms |
496 KB |
Output is correct: Maximum length of a query = 77 |
| 5 |
Correct |
8 ms |
496 KB |
Output is correct: Maximum length of a query = 95 |
| 6 |
Correct |
5 ms |
496 KB |
Output is correct: Maximum length of a query = 87 |
| 7 |
Correct |
7 ms |
496 KB |
Output is correct: Maximum length of a query = 97 |
| 8 |
Correct |
6 ms |
496 KB |
Output is correct: Maximum length of a query = 83 |
| 9 |
Correct |
8 ms |
496 KB |
Output is correct: Maximum length of a query = 101 |
| 10 |
Correct |
5 ms |
616 KB |
Output is correct: Maximum length of a query = 100 |
| 11 |
Correct |
8 ms |
616 KB |
Output is correct: Maximum length of a query = 96 |
| 12 |
Correct |
6 ms |
616 KB |
Output is correct: Maximum length of a query = 100 |
| 13 |
Correct |
11 ms |
688 KB |
Output is correct: Maximum length of a query = 101 |
