#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 1000000007;
vector<int> findSequence(int n) {
vector<int> ans(n, -1);
vi subseq;
int left[2], taken[2];
taken[0] = taken[1] = 0;
int zeros, ones, len = n / 2 + 1, small = 0, big = 1;
zeros = -1;
rep(i, 1, len + 1) {
subseq.pb(0);
if (!isSubsequence(subseq)) {
zeros = i - 1;
break;
}
}
if (zeros == -1) {
subseq.clear();
rep(i, 1, len + 1) {
subseq.pb(1);
if (!isSubsequence(subseq)) {
ones = i - 1;
break;
}
}
zeros = n - ones;
swap(small, big);
} else
ones = n - zeros;
rep(k, 0, 2) {
left[0] = zeros;
left[1] = ones;
taken[0] = taken[1] = 0;
subseq.clear();
int val = k ? 1 : -1, start = k ? 0 : n - 1;
for (int i = start; 0 <= i && i < n; i += val) {
if (ans[i] != -1) break;
vi query = subseq;
int add;
query.insert(query.begin(), big);
rep(j, 0, left[small]) query.insert(query.begin(), small);
if (k) reverse(all(query));
if (sz(query) <= len) {
if (isSubsequence(query))
add = big;
else
add = small;
} else {
query.clear();
rep(j, 0, left[big]) query.pb(big);
rep(j, 0, taken[small] + 1) query.pb(small);
if (sz(query) <= len) {
if (k) reverse(all(query));
if (isSubsequence(query))
add = small;
else
add = big;
} else {
query.clear();
rep(j, 0, left[small]) query.pb(small);
rep(j, 0, taken[big] + 1) query.pb(big);
if (len < sz(query)) break;
if (k) reverse(all(query));
if (isSubsequence(query))
add = big;
else
add = small;
}
}
--left[add];
++taken[add];
subseq.insert(subseq.begin(), add);
ans[i] = add;
}
}
int pos = -1;
rep(i, 0, n) {
if (ans[i] == 1) --ones;
if (!ans[i]) --zeros;
}
//cout << ones << ' ' << zeros << endl;
//rep(i, 0, n) cout << ans[i] << ' ';
//cout << endl;
if (zeros) rep(i, 0, n) if (ans[i] == -1) ans[i] = 0;
if (ones) rep(i, 0, n) if (ans[i] == -1) ans[i] = 1;
return ans;
}
/*
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 = 7, x;
theRealAnswer.resize(n);
rep(i, 0, 1<<n) {
maxQ = 0;
rep(j, 0, n) theRealAnswer[j] = (i & (1 << j)) ? 1 : 0;
//rep(j, 0, n) cout << theRealAnswer[j] << ' ';
//cout << endl<<endl;
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 j = 0; j < ans.size(); j++)
if (ans[j] != theRealAnswer[j]) {
printf("WA position %d\n", j + 1);
for (auto it : ans)
printf("%d ", it);
printf("\n");
cout<<i<<endl;
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:76:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
76 | if (sz(query) <= len) {
| ^
hidden.cpp:87:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
87 | if (sz(query) <= len) {
| ^
hidden.cpp:99:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if (len < sz(query)) break;
| ^
hidden.cpp:116:9: warning: unused variable 'pos' [-Wunused-variable]
116 | int pos = -1;
| ^~~
hidden.cpp:54:15: warning: 'ones' may be used uninitialized in this function [-Wmaybe-uninitialized]
54 | zeros = n - ones;
| ~~~~~~^~~~~~~~~~
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 |
200 KB |
Output is correct: Maximum length of a query = 5 |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct: Maximum length of a query = 6 |
| 3 |
Correct |
1 ms |
200 KB |
Output is correct: Maximum length of a query = 5 |
| 4 |
Correct |
2 ms |
200 KB |
Output is correct: Maximum length of a query = 5 |
| 5 |
Correct |
1 ms |
200 KB |
Output is correct: Maximum length of a query = 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
200 KB |
Output is correct: Maximum length of a query = 83 |
| 2 |
Correct |
8 ms |
328 KB |
Output is correct: Maximum length of a query = 90 |
| 3 |
Correct |
7 ms |
200 KB |
Output is correct: Maximum length of a query = 96 |
| 4 |
Correct |
7 ms |
296 KB |
Output is correct: Maximum length of a query = 77 |
| 5 |
Correct |
7 ms |
296 KB |
Output is correct: Maximum length of a query = 95 |
| 6 |
Correct |
5 ms |
328 KB |
Output is correct: Maximum length of a query = 87 |
| 7 |
Correct |
8 ms |
328 KB |
Output is correct: Maximum length of a query = 97 |
| 8 |
Correct |
6 ms |
328 KB |
Output is correct: Maximum length of a query = 83 |
| 9 |
Correct |
6 ms |
328 KB |
Output is correct: Maximum length of a query = 101 |
| 10 |
Correct |
7 ms |
328 KB |
Output is correct: Maximum length of a query = 100 |
| 11 |
Correct |
7 ms |
328 KB |
Output is correct: Maximum length of a query = 96 |
| 12 |
Correct |
7 ms |
332 KB |
Output is correct: Maximum length of a query = 100 |
| 13 |
Correct |
7 ms |
328 KB |
Output is correct: Maximum length of a query = 101 |
