#include "bits/stdc++.h"
#include "grader.h"
using namespace std;
int dp[202];
int pr[202];
vector<int> ask(vector<pair<int, int> > v1, vector<int> fin) {
for (int i = 0; i <= v1.size(); i++) {
dp[i] = INT_MAX;
pr[i] = -1;
}
dp[0] = 0;
dp[1] = 0;
for (int i = 0; i < v1.size(); i++) {
if (fin[i]) {
int tmp = v1[i].second;
if (i<2)v1[i].second = 1;
dp[i + 2] = min(dp[i + 2], dp[i] + v1[i].second);
if (dp[i + 2] == dp[i] + v1[i].second) {
pr[i + 2] = 2;
}
v1[i].second = tmp;
}
dp[i + 1] = min(dp[i + 1], dp[i] + 1);
if (dp[i + 1] == dp[i] + 1) {
pr[i + 1] = 1;
}
}
vector<int> ret;
int cur = v1.size();
while (cur>1) {
if (pr[cur] == 1) {
ret.push_back(v1[cur - 1].first);
}
else {
if (cur - 2 <= 1)v1[cur - 2].second = 1;
while (v1[cur - 2].second--) {
ret.push_back(v1[cur - 2].first);
}
}
cur -= pr[cur];
}
reverse(ret.begin(), ret.end());
return ret;
}
vector<int> calc(vector<int> v, int add, int lim, int n) {
int z = 0;
vector<pair<int, int> > ar; //kind len
vector<bool> fin;
int rest_add = n - v.size();
for (int i = v.size(); i >= 0; i--) {
vector<int> tmp = v;
tmp.insert(tmp.begin() + v.size() - i, add);
if (isSubsequence(tmp)) {
if (z) {
ar.push_back(make_pair(add ^ true, z));
fin.push_back(true);
z = 0;
}
ar.push_back(make_pair(add, 1));
fin.push_back(false);
rest_add--;
if (i != 0)z++;
}
else {
if (i != 0)z++;
}
}
if (z) {
ar.push_back(make_pair(add ^ true, z));
fin.push_back(true);
}
int idx = 0;
while (rest_add) {
int fc = 0;
int las = 0;
for (int i = 0; i < ar.size(); i++) {
if (fin[i] == false) {
fc++;
las = i;
}
}
if (fc == 1) {
ar[las].second += rest_add;
rest_add = 0;
continue;
}
if (fin[idx] == false) {
vector<int> query;
{
vector<pair<int, int> > v2;
vector<int> f2;
for (int i = 0; i < idx; i++) {
v2.push_back(ar[i]);
f2.push_back(fin[i]);
}
query = ask(v2, f2);
}
int add = ar[idx].second;
add++;
while (add--) {
query.push_back(ar[idx].first);
}
{
vector<pair<int, int> > v2;
vector<int> f2;
for (int i = ar.size() - 1; i > idx; i--) {
v2.push_back(ar[i]);
f2.push_back(fin[i]);
}
auto query2 = ask(v2, f2);
reverse(query2.begin(), query2.end());
for (int el : query2) {
query.push_back(el);
}
}
if (isSubsequence(query)) {
rest_add--;
ar[idx].second++;
}
else {
fin[idx] = true;
}
}
idx++;
idx %= ar.size();
}
vector<int> ans;
for (int i = 0; i < ar.size(); i++) {
while (ar[i].second--) {
ans.push_back(ar[i].first);
}
}
return ans;
}
vector<int> findSequence(int N) {
vector<int> zero;
vector<int> one;
for (int i = 0; i < N / 2 + 1; i++) {
zero.push_back(0);
one.push_back(1);
if (isSubsequence(zero)) {
}
else {
zero.pop_back();
}
if (!isSubsequence(one)) {
one.pop_back();
}
}
while (zero.size() + one.size() < N) {
if (zero.size() > one.size()) {
zero.push_back(0);
}
else {
one.push_back(1);
}
}
if (one.size() > zero.size()) {
return calc(zero, 1, (N) / 2 + 3, N);
}
else {
return calc(one, 0, (N) / 2 + 3, N);
}
}
Compilation message
hidden.cpp: In function 'std::vector<int> ask(std::vector<std::pair<int, int> >, std::vector<int>)':
hidden.cpp:9:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i <= v1.size(); i++) {
~~^~~~~~~~~~~~
hidden.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v1.size(); i++) {
~~^~~~~~~~~~~
hidden.cpp: In function 'std::vector<int> calc(std::vector<int>, int, int, int)':
hidden.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ar.size(); i++) {
~~^~~~~~~~~~~
hidden.cpp:130:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ar.size(); i++) {
~~^~~~~~~~~~~
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:153:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (zero.size() + one.size() < N) {
~~~~~~~~~~~~~~~~~~~~~~~~~^~~
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 |
Incorrect |
2 ms |
308 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 |
6 ms |
488 KB |
Output is not correct: The returned sequence does not match the hidden one |
| 2 |
Halted |
0 ms |
0 KB |
- |
