제출 #950477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950477		glebustim	Crossing (JOI21_crossing)	C++17	26 / 100	7098 ms	7032 KiB

Main

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

const ll MOD = 1e18 + 3, P = 5;
const vector<array<int, 3>> o = {{0, 0, 1}, {0, 1, 0}, {1, 0, 0}, {0, 2, 2}, {2, 0, 2}, {2, 2, 0}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}};
int n;
vi A, B, C;
unordered_set<string> ps;

void all_combs() {
    for (auto x: o) {
        string s(n, '.');
        for (int i = 0; i < n; ++i) {
            int y = (A[i] * x[0] + B[i] * x[1] + C[i] * x[2]) % 3;
            if (y == 0)
                s[i] = 'J';
            else if (y == 1)
                s[i] = 'O';
            else
                s[i] = 'I';
        }
        ps.insert(s);
    }
}

void check_string(string &s) {
    if (ps.find(s) != ps.end())
        cout << "Yes\n";
    else
        cout << "No\n";
}

int main() {
    fast;
    cin >> n;
    A.resize(n);
    B.resize(n);
    C.resize(n);
    string s;
    cin >> s;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'J')
            A[i] = 0;
        else if (s[i] == 'O')
            A[i] = 1;
        else
            A[i] = 2;
    }
    cin >> s;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'J')
            B[i] = 0;
        else if (s[i] == 'O')
            B[i] = 1;
        else
            B[i] = 2;
    }
    cin >> s;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'J')
            C[i] = 0;
        else if (s[i] == 'O')
            C[i] = 1;
        else
            C[i] = 2;
    }
    all_combs();
    int q;
    cin >> q >> s;
    check_string(s);
    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        --l;
        --r;
        for (int i = l; i <= r; ++i)
            s[i] = c;
        check_string(s);
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 23
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51