oj.uz

답안 #984420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
984420 2024-05-16T15:50:13 Z maomao90 Tricolor Lights (JOI24_tricolor) C++17
0 / 100
 1658 ms 3040 KB 
#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 inv(int x, int p) {
        x %= p;
        int res = 1;
        for (int i = 0; i < p - 2; i++) {
            res = res * x % p;
        }
        return res;
    }
    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[i];
                }
            }
            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];
            }
        }
        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:70:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             if (ptr[u] == adj[u].size()) {
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
Bruno.cpp: In function 'void init(int, int)':
Bruno.cpp:88:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |         irgb[rgb[i]] = i;
      |                    ^
Bruno.cpp: In function 'int bruno(std::string)':
Bruno.cpp:120:52: warning: array subscript has type 'char' [-Wchar-subscripts]
  120 |             label[rid / 2].push_back((irgb[u[i + 1]] - irgb[u[i]] + 3) % 3);
      |                                                    ^
Bruno.cpp:120:65: warning: array subscript has type 'char' [-Wchar-subscripts]
  120 |             label[rid / 2].push_back((irgb[u[i + 1]] - irgb[u[i]] + 3) % 3);
      |                                                                 ^

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 1316 KB Output is correct
2 Correct 30 ms 1300 KB Output is correct
3 Correct 26 ms 1392 KB Output is correct
4 Correct 29 ms 1316 KB Output is correct
5 Incorrect 1593 ms 3040 KB Wrong Answer [5]
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 1316 KB Output is correct
2 Correct 30 ms 1300 KB Output is correct
3 Correct 26 ms 1392 KB Output is correct
4 Correct 29 ms 1316 KB Output is correct
5 Incorrect 1593 ms 3040 KB Wrong Answer [5]
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 1316 KB Output is correct
2 Correct 30 ms 1300 KB Output is correct
3 Correct 26 ms 1392 KB Output is correct
4 Correct 29 ms 1316 KB Output is correct
5 Incorrect 1593 ms 3040 KB Wrong Answer [5]
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 1316 KB Output is correct
2 Correct 30 ms 1300 KB Output is correct
3 Correct 26 ms 1392 KB Output is correct
4 Correct 29 ms 1316 KB Output is correct
5 Incorrect 1593 ms 3040 KB Wrong Answer [5]
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1336 KB Output is correct
2 Correct 25 ms 1372 KB Output is correct
3 Correct 26 ms 1316 KB Output is correct
4 Correct 25 ms 1352 KB Output is correct
5 Incorrect 1658 ms 3032 KB Wrong Answer [5]
6 Halted 0 ms 0 KB -