oj.uz

답안 #887146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887146 2023-12-13T21:33:08 Z box Crossing (JOI21_crossing) C++17
0 / 100
 132 ms 1164 KB 
#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 == 'O' ? 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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 852 KB Output is correct
2 Correct 113 ms 852 KB Output is correct
3 Correct 132 ms 868 KB Output is correct
4 Correct 109 ms 1164 KB Output is correct
5 Correct 103 ms 848 KB Output is correct
6 Correct 104 ms 820 KB Output is correct
7 Correct 98 ms 848 KB Output is correct
8 Correct 123 ms 848 KB Output is correct
9 Correct 112 ms 852 KB Output is correct
10 Incorrect 114 ms 792 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 852 KB Output is correct
2 Correct 113 ms 852 KB Output is correct
3 Correct 132 ms 868 KB Output is correct
4 Correct 109 ms 1164 KB Output is correct
5 Correct 103 ms 848 KB Output is correct
6 Correct 104 ms 820 KB Output is correct
7 Correct 98 ms 848 KB Output is correct
8 Correct 123 ms 848 KB Output is correct
9 Correct 112 ms 852 KB Output is correct
10 Incorrect 114 ms 792 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 852 KB Output is correct
2 Correct 113 ms 852 KB Output is correct
3 Correct 132 ms 868 KB Output is correct
4 Correct 109 ms 1164 KB Output is correct
5 Correct 103 ms 848 KB Output is correct
6 Correct 104 ms 820 KB Output is correct
7 Correct 98 ms 848 KB Output is correct
8 Correct 123 ms 848 KB Output is correct
9 Correct 112 ms 852 KB Output is correct
10 Incorrect 114 ms 792 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 852 KB Output is correct
2 Correct 113 ms 852 KB Output is correct
3 Correct 132 ms 868 KB Output is correct
4 Correct 109 ms 1164 KB Output is correct
5 Correct 103 ms 848 KB Output is correct
6 Correct 104 ms 820 KB Output is correct
7 Correct 98 ms 848 KB Output is correct
8 Correct 123 ms 848 KB Output is correct
9 Correct 112 ms 852 KB Output is correct
10 Incorrect 114 ms 792 KB Output isn't correct
11 Halted 0 ms 0 KB -