Submission #710987

#	Time	Username	Problem	Language	Result	Execution time	Memory
710987		zeta7532	Crossing (JOI21_crossing)	C++17	26 / 100	435 ms	2596 KiB

Main

    #include <bits/stdc++.h>
    #pragma GCC target ("avx2")
    #pragma GCC optimize ("O3")
    #pragma GCC optimize ("unroll-loops")
    using namespace std;
    using ll = int;
    const ll mod = 998244353;
    #define fi first
    #define se second
    #define all(x) x.begin(),x.end()
    #define rep(i,x) for(ll i=0;i<x;i++)
    #define faster ios::sync_with_stdio(false);cin.tie(nullptr)
     
    int main(){
        ll N;
        cin >> N;
        if(N>100) return 0;
        vector<ll> rui(N);
        rui[0]=1;
        rep(i,N-1) rui[i+1]=(rui[i]*3)%mod;
        vector<vector<ll>> S(N,vector<ll>(3));
        rep(i,3){
            rep(j,N){
                char c;
                cin >> c;
                if(c=='J') S[j][i]=0;
                if(c=='O') S[j][i]=1;
                if(c=='I') S[j][i]=2;
            }
        }
        set<ll> ans;
        rep(i,27){
            vector<ll> cnt(N,0);
            ll i0=i%3;
            ll i1=(i%9)/3;
            ll i2=i/9;
            if((i0+i1+i2)%3!=1) continue;
            rep(j,N) cnt[j]+=S[j][0]*i0;
            rep(j,N) cnt[j]+=S[j][1]*i1;
            rep(j,N) cnt[j]+=S[j][2]*i2;
            rep(j,N) cnt[j]%=3;
            ll ANS=0;
            rep(j,N) ANS=(ANS+cnt[j]*rui[j])%mod;
            ans.insert(ANS);
        }
        ll Q;
        cin >> Q;
        vector<ll> T(N);
        rep(i,N){
            char c;
            cin >> c;
            if(c=='J') T[i]=0;
            if(c=='O') T[i]=1;
            if(c=='I') T[i]=2;
        }
        rep(i,Q+1){
            ll x=0;
            rep(j,N) x=(x+T[j]*rui[j])%mod;
            if(ans.find(x)!=ans.end()){
                cout << "Yes" << '\n';
            }    
            else cout << "No" << '\n';
            if(i==Q) break;
            ll l,r;
            char c;
            cin >> l >> r >> c;
            l--,r--;
            ll C=-1;
            if(c=='J') C=0;
            if(c=='O') C=1;
            if(c=='I') C=2;
            for(ll j=l;j<=r;j++){
                T[j]=C; 
            }
        }
    }

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