Submission #971438

#	Time	Username	Problem	Language	Result	Execution time	Memory
971438		Acanikolic	Crossing (JOI21_crossing)	C++14	26 / 100	7102 ms	13372 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int P = 31;

const int mod = 1e9 + 7;

string resi(string a,string b) {
    string res;
    for(int i = 0; i < a.size(); i++) res += 'J';
    for(int i = 1; i < a.size(); i++) {
        if(a[i] == b[i]) res[i] = a[i];
        else {
            bool J = false,O = false,I = false;
            if(a[i] == 'J' || b[i] == 'J') J = true;
            if(a[i] == 'O' || b[i] == 'O') O = true;
            if(a[i] == 'I' || b[i] == 'I') I = true;
            if(!J) res[i] = 'J';
            else if(!O) res[i] = 'O';
            else res[i] = 'I';
        }
    }
    return res;
}

int add(int a,int b) {
    return (a + b) % mod;
}

int mul(int a,int b) {
    return (a * b) % mod;
}

struct hes {
    // h[i] = h[i - 1] + (pw[i] * s[i] - 'a' + 1)
    string s;
    vector<int>pw,val;
    void build(string t,int n) {
        s = t;
        pw.resize(n + 1);
        val.resize(n + 1);
        pw[0] = 1;
        for(int i = 1; i <= n; i++) pw[i] = mul(pw[i - 1],P);
        for(int i = 1; i <= n; i++) val[i] = add(val[i - 1],mul(pw[i],(s[i] - 'A' + 1)));
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    set<string>st;
    string a,b,c;
    cin >> a >> b >> c;
    a = '.' + a;
    b = '.' + b;
    c = '.' + c;
    st.insert(a);
    st.insert(b);
    st.insert(c);
    st.insert(resi(a,c));
    st.insert(resi(b,c));
    st.insert(resi(a,b));
    st.insert(resi(resi(a,b),c));
    st.insert(resi(resi(b,a),c));
    st.insert(resi(resi(c,a),b));
    st.insert(resi(resi(a,c),b));
    st.insert(resi(resi(b,c),a));
    st.insert(resi(resi(c,b),a));
    vector<string>vec;
    for(auto X : st) vec.push_back(X);
    int K = vec.size();
    vector<hes>niz(K);
    for(int i = 0; i < K; i++) {
        niz[i].build(vec[i],n);
    }
    int Q;
    cin >> Q;
    string str;
    cin >> str;
    str = '.' + str;
    hes T;
    T.build(str,n);
    bool ok = false;
    for(int i = 0; i < K; i++) if(T.val[n] == niz[i].val[n]) ok = true;
    cout << (ok ? "Yes\n" : "No\n");
    while(Q--) {
        int l,r;
        char c;
        cin >> l >> r >> c;
        for(int i = l; i <= r; i++) str[i] = c;
        T.build(str,n);
        bool ok = false;
        for(int i = 0; i < K; i++) if(T.val[n] == niz[i].val[n]) ok = true;
        cout << (ok ? "Yes\n" : "No\n");
    }
}
/*
JOJO
JJOI
OJOO

a ^ b
a ^ c
b ^ c

a ^ a ^ b = b
a ^ a ^ c = c
a ^ b ^ c novo

b ^ a ^ b = a
b ^ a ^ c =
*/

Compilation message (stderr)

Main.cpp: In function 'std::string resi(std::string, std::string)':
Main.cpp:13:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < a.size(); i++) res += 'J';
      |                    ~~^~~~~~~~~~
Main.cpp:14:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 1; i < a.size(); i++) {
      |                    ~~^~~~~~~~~~
Main.cpp:17:38: warning: variable 'I' set but not used [-Wunused-but-set-variable]
   17 |             bool J = false,O = false,I = false;
      |                                      ^

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