Submission #788096

#	Time	Username	Problem	Language	Result	Execution time	Memory
788096		anton	Crossing (JOI21_crossing)	C++17	26 / 100	7044 ms	3792 KiB

Main

#include<bits/stdc++.h>

using namespace std;


const int MAX_N = 2*1e5;

int n, q, v[3][3], t[MAX_N][2];
bool is_set[3][3];
string s[3], r;

bool upd_val(int x, int y, int val){
    if(!is_set[x][y]){
        is_set[x][y] = true;
        v[x][y] = val;
    }
    else{
        if(v[x][y] != val){
            return false;
        }
    }
    return true;
}

signed main(){
    cin>>n;

    for(int i = 0; i<3; i++){
        cin>>s[i];
    }

    map<char, int> m;
    m['J'] = 0;
    m['O'] = 1;
    m['I'] = 2;

    for(int i = 0; i<n; i++){
        t[i][0] =(m[s[1][i]] -m[s[0][i]] +3)%3;
        t[i][1] =(m[s[2][i]] - m[s[0][i]] + 3)%3;

        //cout<<t[i][0]<<" "<<t[i][1]<<endl;
    }

    fill(&is_set[0][0], &is_set[0][0] + sizeof(is_set), false);

    cin>>q;
    cin>>r;

    bool ok = true;

    is_set[0][0] = true;
    v[0][0] =0;

    for(int i = -1; i<q; i++){

        if(i >=0){
            int l, ri;
            char c;
            cin>>l>>ri>>c;
            l--;
            ri--;

            for(int p = l; p<=ri; p++){
                r[p] = c;
            }
        }

        //cout<<r<<endl;
        ok = true;
        fill(&is_set[0][0], &is_set[0][0] + sizeof(is_set), false);
        for(int i = 0; i<n; i++){
            ok &= upd_val(t[i][0], t[i][1], (m[r[i]] - m[s[0][i]] + 3)%3);
        }

        for(int i = 0; i<9; i++){
            for(int b= 0; b<9; b++){
                for(int e = 0; e<9; e++){
                    if(is_set[b/3][b%3] && is_set[e/3][e%3]){
                        ok &= upd_val((e/3 + b/3)%3, (e+b)%3, (v[e/3][e%3] + v[b/3][b%3])%3);
                    }
                }
            }
        }

        if(ok){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }   
    }
}

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