#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wparentheses"
#include <bits/stdc++.h>
#include "grader.h"
#define all(i) (i).begin(), (i).end()
#define random random_device rd; mt19937 rng(rd())
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << ':';
for (T ii : j) i << ' ' << ii;
return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
if (_split)
cerr << ", ";
cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
cerr << '[';
for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;
bool isSubsequence(vector<int> s);
vector<int> findSequence(int n) {
int mx = n / 2 + 3;
int zro = -1;
for (int i = 1; i <= mx; ++i)
if (!isSubsequence(vector<int>(i, 0))) {
zro = i - 1;
break;
}
if (zro == -1) {
for (int i = 1; i <= mx; ++i)
if (!isSubsequence(vector<int>(i, 1))) {
zro = n - i + 1;
break;
}
}
int one = n - zro;
if (zro <= one) {
auto gen = [&](int pos, int cnt) {
vector<int> res(pos, 0);
res.insert(res.end(), cnt, 1);
res.insert(res.end(), zro - pos, 0);
return res;
};
int a[zro + 1]{}, rem = zro + 1;
bool ok[zro + 1]{};
for (int i = 0; i < zro + 1; ++i) {
for (int j = 1; zro + j <= mx; ++j)
if (isSubsequence(gen(i, j)))
++a[i], --one;
else {
ok[i] = true;
--rem;
break;
}
}
auto gen2 = [&](int pos, int cnt) {
deque<int> res(cnt, 1);
int last = 0;
for (int i = pos - 1; ~i; --i) {
if (last == 0) {
if (a[i] == 1)
res.push_front(1);
else if (a[i] > 1)
res.push_front(1), last = 1;
}
else {
res.push_front(0);
if (!a[i])
last = 0;
}
}
last = 0;
for (int i = pos; i < zro; ++i) {
if (last == 0) {
if (a[i + 1] == 1)
res.push_back(1);
else if (a[i + 1] > 1)
res.push_back(1), last = 1;
}
else {
res.push_back(0);
if (!a[i + 1])
last = 0;
}
}
return vector<int>(all(res));
};
for (int i = 0; i < zro + 1 && rem > 1 && one; ++i)
if (!ok[i]) {
vector<int> tmp = gen2(i, a[i] + 1);
while (tmp.size() <= mx) {
if (isSubsequence(tmp))
++a[i], --one;
else {
ok[i] = true;
--rem;
break;
}
tmp = gen2(i, a[i] + 1);
}
}
for (int i = 0; i < zro + 1; ++i)
if (!ok[i])
a[i] += one, one = 0;
vector<int> ans;
for (int i = 0; i < zro + 1; ++i)
ans.insert(ans.end(), a[i], 1), ans.push_back(0);
ans.pop_back();
return ans;
}
else {
auto gen = [&](int pos, int cnt) {
vector<int> res(pos, 1);
res.insert(res.end(), cnt, 0);
res.insert(res.end(), one - pos, 1);
return res;
};
int a[one + 1]{}, rem = one + 1;
bool ok[one + 1]{};
for (int i = 0; i < one + 1; ++i) {
for (int j = 1; one + j <= mx; ++j)
if (isSubsequence(gen(i, j)))
++a[i], --zro;
else {
ok[i] = true;
--rem;
break;
}
}
auto gen2 = [&](int pos, int cnt) {
deque<int> res(cnt, 0);
int last = 1;
for (int i = pos - 1; ~i; --i) {
if (last == 1) {
if (a[i] == 1)
res.push_front(0);
else if (a[i] > 1)
res.push_front(0), last = 0;
}
else {
res.push_front(1);
if (!a[i])
last = 1;
}
}
last = 1;
for (int i = pos; i < one; ++i) {
if (last == 1) {
if (a[i + 1] == 1)
res.push_back(0);
else if (a[i + 1] > 1)
res.push_back(0), last = 0;
}
else {
res.push_back(1);
if (!a[i + 1])
last = 1;
}
}
return vector<int>(all(res));
};
for (int i = 0; i < one + 1 && rem > 1 && zro; ++i)
if (!ok[i]) {
vector<int> tmp = gen2(i, a[i] + 1);
while (tmp.size() <= mx) {
if (isSubsequence(tmp))
++a[i], --zro;
else {
ok[i] = true;
--rem;
break;
}
tmp = gen2(i, a[i] + 1);
}
}
for (int i = 0; i < one + 1; ++i)
if (!ok[i])
a[i] += zro, zro = 0;
vector<int> ans;
for (int i = 0; i < one + 1; ++i)
ans.insert(ans.end(), a[i], 0), ans.push_back(1);
ans.pop_back();
return ans;
}
}
Compilation message
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:117:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
117 | while (tmp.size() <= mx) {
| ~~~~~~~~~~~^~~~~
hidden.cpp:191:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
191 | while (tmp.size() <= mx) {
| ~~~~~~~~~~~^~~~~
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 |
Partially correct |
1 ms |
200 KB |
Output is partially correct: Maximum length of a query = 7 |
| 2 |
Partially correct |
1 ms |
200 KB |
Output is partially correct: Maximum length of a query = 8 |
| 3 |
Partially correct |
1 ms |
200 KB |
Output is partially correct: Maximum length of a query = 7 |
| 4 |
Partially correct |
1 ms |
200 KB |
Output is partially correct: Maximum length of a query = 7 |
| 5 |
Partially correct |
1 ms |
200 KB |
Output is partially correct: Maximum length of a query = 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
4 ms |
292 KB |
Output is partially correct: Maximum length of a query = 85 |
| 2 |
Partially correct |
5 ms |
296 KB |
Output is partially correct: Maximum length of a query = 92 |
| 3 |
Runtime error |
13 ms |
544 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
