Submission #984428

#	Time	Username	Problem	Language	Result	Execution time	Memory
984428		maomao90	Tricolor Lights (JOI24_tricolor)	C++17	100 / 100	84 ms	4376 KiB

Anna

#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]);
    }
    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++;
        }
    }
    return {res, min(28, n)};
}

Bruno

#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];
                }
            }
            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;
    }
    for (int o = 0; o < 9; o++) {
        bool bad = 0;
        vector<int> label[4];
        for (int i = 0; i < l; i++) {
            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];
            }
        }
        int id = crt(a, m);
        return id * 9 + o + 1;
    }
    assert(0);
}

Compilation message (stderr)

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:80:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             if (ptr[u] == adj[u].size()) {
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
Bruno.cpp: In function 'void init(int, int)':
Bruno.cpp:98:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |         irgb[rgb[i]] = i;
      |                    ^
Bruno.cpp: In function 'int bruno(std::string)':
Bruno.cpp:127:52: warning: array subscript has type 'char' [-Wchar-subscripts]
  127 |             label[rid / 2].push_back((irgb[u[i + 1]] - irgb[u[i]] + 3) % 3);
      |                                                    ^
Bruno.cpp:127:65: warning: array subscript has type 'char' [-Wchar-subscripts]
  127 |             label[rid / 2].push_back((irgb[u[i + 1]] - irgb[u[i]] + 3) % 3);
      |                                                                 ^

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 15 / 15
• Subtask 5: 70 / 70