Submission #887144

#	Time	Username	Problem	Language	Result	Execution time	Memory
887144		box	Crossing (JOI21_crossing)	C++17	0 / 100	130 ms	2544 KiB

Main

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

#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 2e5, P1 = 1e9 + 7, P2 = 1e9 + 9;

string operator+(string one, const string two) {
    static char all = 'J' ^ 'O' ^ 'I';
    for (int i = 0; i < sz(one); i++)
        one[i] = one[i] == two[i] ? one[i] : (one[i] ^ two[i] ^ all);
    return one;
}

i64 hsh(const string s) {
    i64 one = 0, two = 0;
    for (char c : s) {
        int i = c == 'J' ? 0 : c == 'I' ? 1 : 2;
        one = (one * 3 + i) % P1;
        two = (two * 3 + i) % P2;
    }
    return one * P2 + two;
}

mt19937 rng(1234);

string gen(int n) {
    string s(n, '?');
    for (int i = 0; i < n; i++) s[i] = "JOI"[rng() % 3];
    return s;
}

int n, q;
vector<string> v;
unordered_set<i64> s;

void expand() {
    for (string t : v) s.insert(hsh(t));
    while (1) {
        int m = sz(v);
        for (int i = 0; i < m; i++) for (int j = i + 1; j < m; j++) {
            string t = v[i] + v[j];
            i64 h = hsh(t);
            if (!s.count(h)) {
                s.insert(h);
                v.push_back(t);
            }
        }
        if (sz(v) == m) break;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int rep = 0; rep < 3; rep++) {
        string s;
        cin >> s;
        v.push_back(s);
    }
    expand();
    cin >> q;
    string t;
    cin >> t;
    cout << (s.count(hsh(t)) ? "Yes\n" : "No\n");
    while (q--) {
        int l, r; char c;
        cin >> l >> r >> c, l--, r--;
        for (int i = l; i <= r; i++) t[i] = c;
        cout << (s.count(hsh(t)) ? "Yes\n" : "No\n");
    }

}

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