#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int nmax = 1000;
pair<bitset<nmax>, bool> ask_kmp(vector<bool> suffix) {
suffix.insert(suffix.begin(), 0);
vector<int> a(suffix.size() + 1, -1), b(suffix.size() + 1, -1);
for (int i = 0; i <= suffix.size(); ++i) {
// suffix[..i] + 0 ->
// on failure
for (int j = min((int)suffix.size(), i + 1); j >= 0; --j) {
// check for suffix[..i] + (value) sfx = suffix[..j]
bool zero_valid = true, one_valid = true;
for (int k = 0; j - 1 - k >= 0; ++k) {
bool added = k == 0 ? 0 : suffix[i - k];
if (added != suffix[j - 1 - k]) {
zero_valid = false;
}
bool added2 = k == 0 ? 1 : suffix[i - k];
if (added2 != suffix[j - 1 - k]) {
one_valid = false;
}
}
if (zero_valid) a[i] = max(a[i], j);
if (one_valid) b[i] = max(b[i], j);
}
}
int res = Query(a.size(), a, b);
bitset<nmax> ret;
ret[nmax - suffix.size()] = true;
// total match (with zero added) -> It's zero, else it's one
return {ret, res == suffix.size() ? false : true};
}
pair<bitset<nmax>, bool> ask_prefix(int i) {
vector<int> a(i + 3), b(i + 3);
for (int j = 0; j < i; ++j) {
a[j] = j + 1, b[j] = j + 1;
}
a[i] = i + 1;
b[i] = i + 2;
a[i + 1] = b[i + 1] = i + 1;
a[i + 2] = b[i + 2] = i + 2;
int res = Query(a.size(), a, b);
bitset<nmax> ret;
ret[i] = true;
// res == i + 2 -> it's 1, else zero
return {ret, res == i + 2};
}
pair<bitset<nmax>, bool> ask_period(int i, int j) {
// calculate sum S_{i*k+j}
bitset<nmax> summed;
for (int k = 0; i * k + j < nmax; ++k) summed[i * k + j] = true;
vector<int> a(2 * i), b(2 * i);
for (int k = 0; k < i; ++k) {
b[k] = (k + 1) % i;
a[k] = (k + 1) % i;
b[k + i] = (k + 1) % i + i;
a[k + i] = (k + 1) % i + i;
}
b[j] = (j + 1) % i + i;
b[j + i] = (j + 1) % i;
int res = Query(2 * i, a, b);
bool sum = res >= i;
return {summed, sum};
}
vector<bool> gaussian_elimination(vector<bitset<nmax>> set, vector<bool> values) {
int fst_idx = 0;
for (int bit = 0; bit < nmax; ++bit) {
for (int i = fst_idx; i < set.size(); ++i) {
if (set[i][bit]) {
swap(set[fst_idx], set[i]);
swap(values[fst_idx], values[i]);
break;
}
}
if (fst_idx == set.size() || !set[fst_idx][bit]) continue;
for (int i = fst_idx + 1; i < set.size(); ++i) {
if (!set[i][bit]) continue;
set[i] ^= set[fst_idx];
values[i] = values[i] ^ values[fst_idx];
}
fst_idx += 1;
}
for (int i = set.size() - 1; i >= 0; --i) {
for (int j = 0; j < i; ++j) {
if (set[j][i]) {
set[j] ^= set[i];
values[j] = values[j] ^ values[i];
}
}
}
return values;
}
} // namespace
bitset<1527> is_in("000000000000000000000000001111111111111111111111111000000000000000000000000000000111111111111111111110000000111111111111111111111111111111111111111111000000000000000000000000000000001111111111111111011111111111111111111111111111111111111111111110000000000000000000000001111111111111111111111000000000000000000000111111111111111111111111000000000000000000000000111111111111111111110111111111111111111111111111111111111111111000000000000000000000000000000111111111111011111111111111111111111111111111111111110000000000000000000000001111111111111111000000000000000111111111111111111111111000000000000000000001111111111111111110111111111111111111111111111111111111000000000000000000000000111111111111000000000001111111111111111111111110000000000000000001111111111111111000000000000011111111111111111111000000000000000011111111111111110111111111111111111111111111111000000000000000000000011111111011111111111111111111111111110000000000000000111111111111000000000111111111111111111000000000000001111111111110000011111111111111111111000000000000000011111111011111111111111111111110000000000001111111111000000000111111111111000000000000111111110111111111111111111000000000000111111011111111111111110000000011111111000000011111111000000001111110111111111111000000001111011111111110000001111000111111000011110111111000011011110011011011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111");
std::string Solve(int N) {
vector<bitset<nmax>> sets;
vector<bool> values;
int considered = 0;
for (int i = 0; i + 3 <= 102; ++i) {
if (!is_in[considered++]) continue;
auto [row, res] = ask_prefix(i);
sets.push_back(row);
values.push_back(res);
}
vector<bool> prefix;
for (int i = nmax - 1; i >= 0; --i) {
int len = nmax - i;
if (len + 1 > 102) break;
if (!is_in[considered++]) continue;
auto [row, res] = ask_kmp(prefix);
sets.push_back(row);
values.push_back(res);
prefix.insert(prefix.begin(), res);
}
for (int i = 1; i <= 51; ++i) {
for (int j = 0; j < i; ++j) {
if (!is_in[considered++]) continue;
// sun S_{k*i+j}
auto [row, res] = ask_period(i, j);
sets.push_back(row);
values.push_back(res);
}
}
auto s = gaussian_elimination(sets, values);
string ret(nmax, '0');
for (int i = 0; i < nmax; ++i) ret[i] = s[i] ? '1' : '0';
return ret;
}
#ifndef EVAL
#include "grader.cpp"
#endif
Compilation message
ancient2.cpp: In function 'std::pair<std::bitset<1000>, bool> {anonymous}::ask_kmp(std::vector<bool>)':
ancient2.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int i = 0; i <= suffix.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~
ancient2.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | return {ret, res == suffix.size() ? false : true};
| ~~~~^~~~~~~~~~~~~~~~
ancient2.cpp: In function 'std::vector<bool> {anonymous}::gaussian_elimination(std::vector<std::bitset<1000> >, std::vector<bool>)':
ancient2.cpp:85:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<1000> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = fst_idx; i < set.size(); ++i) {
| ~~^~~~~~~~~~~~
ancient2.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<1000> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | if (fst_idx == set.size() || !set[fst_idx][bit]) continue;
| ~~~~~~~~^~~~~~~~~~~~~
ancient2.cpp:93:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<1000> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = fst_idx + 1; i < set.size(); ++i) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
848 KB |
Output is correct |
| 2 |
Correct |
33 ms |
848 KB |
Output is correct |
| 3 |
Correct |
24 ms |
600 KB |
Output is correct |
| 4 |
Correct |
23 ms |
600 KB |
Output is correct |
| 5 |
Correct |
36 ms |
592 KB |
Output is correct |
| 6 |
Correct |
27 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
27 ms |
636 KB |
Output is correct |
| 8 |
Correct |
30 ms |
752 KB |
Output is correct |
| 9 |
Correct |
23 ms |
556 KB |
Output is correct |
| 10 |
Correct |
30 ms |
1044 KB |
Output is correct |
| 11 |
Correct |
25 ms |
684 KB |
Output is correct |
| 12 |
Correct |
32 ms |
592 KB |
Output is correct |
| 13 |
Correct |
25 ms |
848 KB |
Output is correct |
| 14 |
Correct |
33 ms |
600 KB |
Output is correct |
| 15 |
Correct |
26 ms |
592 KB |
Output is correct |
| 16 |
Correct |
22 ms |
560 KB |
Output is correct |
| 17 |
Correct |
23 ms |
600 KB |
Output is correct |
| 18 |
Correct |
34 ms |
656 KB |
Output is correct |
| 19 |
Correct |
25 ms |
728 KB |
Output is correct |
| 20 |
Correct |
26 ms |
1616 KB |
Output is correct |
| 21 |
Correct |
28 ms |
716 KB |
Output is correct |
| 22 |
Correct |
26 ms |
912 KB |
Output is correct |
| 23 |
Correct |
27 ms |
848 KB |
Output is correct |
| 24 |
Correct |
25 ms |
600 KB |
Output is correct |
| 25 |
Correct |
25 ms |
600 KB |
Output is correct |
| 26 |
Correct |
37 ms |
592 KB |
Output is correct |
| 27 |
Correct |
34 ms |
644 KB |
Output is correct |
| 28 |
Correct |
37 ms |
848 KB |
Output is correct |
| 29 |
Correct |
31 ms |
596 KB |
Output is correct |
| 30 |
Correct |
33 ms |
600 KB |
Output is correct |
| 31 |
Correct |
28 ms |
592 KB |
Output is correct |
| 32 |
Correct |
27 ms |
600 KB |
Output is correct |
| 33 |
Correct |
24 ms |
692 KB |
Output is correct |
| 34 |
Correct |
25 ms |
592 KB |
Output is correct |
| 35 |
Correct |
24 ms |
600 KB |
Output is correct |
| 36 |
Correct |
32 ms |
848 KB |
Output is correct |
| 37 |
Correct |
23 ms |
600 KB |
Output is correct |
| 38 |
Correct |
39 ms |
592 KB |
Output is correct |
| 39 |
Correct |
32 ms |
600 KB |
Output is correct |
| 40 |
Correct |
32 ms |
612 KB |
Output is correct |
| 41 |
Correct |
34 ms |
600 KB |
Output is correct |
| 42 |
Correct |
34 ms |
708 KB |
Output is correct |
| 43 |
Correct |
32 ms |
600 KB |
Output is correct |
| 44 |
Correct |
32 ms |
652 KB |
Output is correct |
| 45 |
Correct |
31 ms |
592 KB |
Output is correct |
| 46 |
Correct |
32 ms |
600 KB |
Output is correct |
| 47 |
Correct |
33 ms |
592 KB |
Output is correct |
| 48 |
Correct |
37 ms |
492 KB |
Output is correct |
| 49 |
Correct |
36 ms |
668 KB |
Output is correct |
| 50 |
Correct |
32 ms |
640 KB |
Output is correct |
| 51 |
Correct |
38 ms |
600 KB |
Output is correct |
| 52 |
Correct |
34 ms |
708 KB |
Output is correct |
| 53 |
Correct |
31 ms |
592 KB |
Output is correct |
| 54 |
Correct |
39 ms |
592 KB |
Output is correct |
| 55 |
Correct |
34 ms |
600 KB |
Output is correct |
| 56 |
Correct |
31 ms |
600 KB |
Output is correct |
| 57 |
Correct |
27 ms |
592 KB |
Output is correct |
| 58 |
Correct |
35 ms |
820 KB |
Output is correct |
| 59 |
Correct |
24 ms |
668 KB |
Output is correct |
| 60 |
Correct |
32 ms |
592 KB |
Output is correct |
| 61 |
Correct |
36 ms |
1320 KB |
Output is correct |
| 62 |
Correct |
33 ms |
600 KB |
Output is correct |
| 63 |
Correct |
32 ms |
600 KB |
Output is correct |
