#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;
namespace {
const string rgb = "RGB";
const vector<string> illegal[4] = {
{},
{"010", "101"},
{"010", "101", "000"},
{"010", "101", "020", "202"}
};
vector<int> debrujin(vector<string> illegal) {
vector<int> adj[9];
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
for (int c = 0; c < 3; c++) {
if (a != 0 && b != 0 && c != 0) {
continue;
}
bool bad = 0;
for (string s : illegal) {
if (s[0] - '0' == a && s[1] - '0' == b && s[2] - '0' == c) {
bad = 1;
break;
}
}
if (bad) {
continue;
}
adj[a * 3 + b].push_back(b * 3 + c);
}
}
}
int ptr[9];
memset(ptr, 0, sizeof ptr);
vector<int> stk;
stk.push_back(0);
vector<int> res;
while (!stk.empty()) {
int u = stk.back();
if (ptr[u] == adj[u].size()) {
stk.pop_back();
res.push_back(u % 3);
} else {
stk.push_back(adj[u][ptr[u]++]);
}
}
res.pop_back();
return res;
}
int n;
string s;
vector<int> key[4];
}
pair<string, int> anna(int N, string S) {
n = N; s = S;
for (int i = 0; i < 4; i++) {
key[i] = debrujin(illegal[i]);
for (int j : key[i]) {
cerr << j;
}
cerr << '\n';
}
string res(n, '?');
for (int i = 0; i < n; i++) {
int rid = i % 9;
if (rid == 8 || i + 1 == n) {
for (char c : rgb) {
if (c != s[i] && c != res[i - 1]) {
res[i] = c;
break;
}
}
} else {
for (int l = 0; l < 3; l++) {
int r = (l +
key[rid / 2][(i / 9) % key[rid / 2].size()]) % 3;
if (s[i] != rgb[l] && s[i + 1] != rgb[r]) {
res[i] = rgb[l];
res[i + 1] = rgb[r];
break;
}
}
i++;
}
}
cerr << res << '\n';
return {res, min(28, n)};
}
#include <bits/stdc++.h>
#include "Bruno.h"
using namespace std;
namespace {
int extended_gcd(int a, int b, int &x, int &y) {
pair<int, int> va = {1, 0}, vb = {0, 1};
while (b) {
int k = a / b;
a -= k * b;
va.first -= k * vb.first;
va.second -= k * vb.second;
swap(a, b);
swap(va, vb);
}
tie(x, y) = va;
return a;
}
int inv(int x, int p) {
int res, _;
extended_gcd(x, p, res, _);
return (res % p + p) % p;
}
int crt(vector<int> a, vector<int> m) {
int n = a.size();
int mod = 1;
for (int i = 0; i < n; i++) {
mod *= m[i];
}
int res = 0;
for (int i = 0; i < n; i++) {
int y = 1;
for (int j = 0; j < n; j++) {
if (i != j) {
y *= m[j];
}
}
cerr << i << ": " << a[i] << ' ' << y << ' ' << inv(y, m[i]) << '\n';
res += a[i] * y * inv(y, m[i]);
}
return res % mod;
}
const string rgb = "RGB";
const vector<string> illegal[4] = {
{},
{"010", "101"},
{"010", "101", "000"},
{"010", "101", "020", "202"}
};
int irgb[300];
vector<int> debrujin(vector<string> illegal) {
vector<int> adj[9];
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
for (int c = 0; c < 3; c++) {
if (a != 0 && b != 0 && c != 0) {
continue;
}
bool bad = 0;
for (string s : illegal) {
if (s[0] - '0' == a && s[1] - '0' == b && s[2] - '0' == c) {
bad = 1;
break;
}
}
if (bad) {
continue;
}
adj[a * 3 + b].push_back(b * 3 + c);
}
}
}
int ptr[9];
memset(ptr, 0, sizeof ptr);
vector<int> stk;
stk.push_back(0);
vector<int> res;
while (!stk.empty()) {
int u = stk.back();
if (ptr[u] == adj[u].size()) {
stk.pop_back();
res.push_back(u % 3);
} else {
stk.push_back(adj[u][ptr[u]++]);
}
}
res.pop_back();
return res;
}
int n, l;
vector<int> key[4];
}
void init(int N, int l) {
n = N;
::l = l;
for (int i = 0; i < 3; i++) {
irgb[rgb[i]] = i;
}
for (int i = 0; i < 4; i++) {
key[i] = debrujin(illegal[i]);
}
}
int bruno(string u) {
if (n == l) {
return 1;
}
cerr << u << '\n';
for (int o = 0; o < 9; o++) {
cerr << o << '\n';
bool bad = 0;
vector<int> label[4];
for (int i = 0; i < l; i++) {
cerr << ' ' << i << '\n';
int rid = (i + o) % 9;
if (rid % 2 == 1) {
continue;
}
if (rid == 8) {
if (i && u[i - 1] == u[i]) {
bad = 1;
break;
}
continue;
}
if (i + 1 == l) {
break;
}
label[rid / 2].push_back((irgb[u[i + 1]] - irgb[u[i]] + 3) % 3);
i++;
}
if (bad) {
continue;
}
for (int t = 0; t < 4; t++) {
bool has0 = 0;
for (int x : label[t]) {
if (x == 0) {
has0 = 1;
break;
}
}
if (!has0) {
bad = 1;
break;
}
}
if (bad) {
continue;
}
vector<int> a(4), m(4);
for (int t = 0; t < 4; t++) {
m[t] = key[t].size();
for (int i = 0; i < m[t]; i++) {
bool bad = 0;
for (int j = 0; j < 3; j++) {
if (key[t][(i + j) % m[t]] != label[t][j]) {
bad = 1;
break;
}
}
if (!bad) {
a[t] = i;
break;
}
}
if (t * 2 < o) {
a[t] = (a[t] - 1 + m[t]) % m[t];
}
cerr << t << ": " << a[t] << '\n';
}
int id = crt(a, m);
cerr << id << ' ' << o << '\n';
return id * 9 + o + 1;
}
assert(0);
}
Compilation message
Anna.cpp: In function 'std::vector<int> {anonymous}::debrujin(std::vector<std::__cxx11::basic_string<char> >)':
Anna.cpp:43:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if (ptr[u] == adj[u].size()) {
| ~~~~~~~^~~~~~~~~~~~~~~~
Bruno.cpp: In function 'std::vector<int> {anonymous}::debrujin(std::vector<std::__cxx11::basic_string<char> >)':
Bruno.cpp:81:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if (ptr[u] == adj[u].size()) {
| ~~~~~~~^~~~~~~~~~~~~~~~
Bruno.cpp: In function 'void init(int, int)':
Bruno.cpp:99:20: warning: array subscript has type 'char' [-Wchar-subscripts]
99 | irgb[rgb[i]] = i;
| ^
Bruno.cpp: In function 'int bruno(std::string)':
Bruno.cpp:131:52: warning: array subscript has type 'char' [-Wchar-subscripts]
131 | label[rid / 2].push_back((irgb[u[i + 1]] - irgb[u[i]] + 3) % 3);
| ^
Bruno.cpp:131:65: warning: array subscript has type 'char' [-Wchar-subscripts]
131 | label[rid / 2].push_back((irgb[u[i + 1]] - irgb[u[i]] + 3) % 3);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1324 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
25 ms |
1332 KB |
Output is correct |
| 4 |
Correct |
27 ms |
1236 KB |
Output is correct |
| 5 |
Execution timed out |
2013 ms |
3872 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1324 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
25 ms |
1332 KB |
Output is correct |
| 4 |
Correct |
27 ms |
1236 KB |
Output is correct |
| 5 |
Execution timed out |
2013 ms |
3872 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1324 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
25 ms |
1332 KB |
Output is correct |
| 4 |
Correct |
27 ms |
1236 KB |
Output is correct |
| 5 |
Execution timed out |
2013 ms |
3872 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1324 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
25 ms |
1332 KB |
Output is correct |
| 4 |
Correct |
27 ms |
1236 KB |
Output is correct |
| 5 |
Execution timed out |
2013 ms |
3872 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1324 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1392 KB |
Output is correct |
| 3 |
Correct |
24 ms |
1396 KB |
Output is correct |
| 4 |
Correct |
28 ms |
1288 KB |
Output is correct |
| 5 |
Execution timed out |
2031 ms |
3756 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
