Submission #419982

#	Time	Username	Problem	Language	Result	Execution time	Memory
419982		davi_bart	Crossing (JOI21_crossing)	C++14	26 / 100	7015 ms	5656 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N,Q;
set<string> k;
string a,b,c;
string t;
vector<vector<int> > h;
const int dim=100;
const int p=257,mod=1e9+9;
vector<int> pot;
vector<int> tt;
int hasha(string q){
    int l=0;
    for(auto k:q)l=(l*p+k)%mod;
    for(int i=q.size();i<dim;i++)l=l*p%mod;
    return l;
}
void solve(){
    for(auto v:h){
        bool ok=1;
        for(int i=0;i<v.size();i++)if(v[i]!=tt[i])ok=0;
        if(ok){
            cout<<"Yes\n";
            return;
        }
    }
    cout<<"No\n";
}
string cross(string x,string y){
    string ans="";
    vector<char> s={'I','J','O'};
    for(int i=0;i<x.size();i++){
        if(x[i]==y[i])ans+=x[i];
        else{
            for(auto h:s)if(x[i]!=h && y[i]!=h)ans+=h;
        }
    }
    return ans;
}
void calc(){
    while(1){
        bool ok=0;
        for(auto x:k){
            for(auto y:k){
                string h=cross(x,y);
                if(k.count(h))continue;
                ok=1;
                k.insert(h);
            }
        }
        if(!ok)break;
    }
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
    cin>>N>>a>>b>>c>>Q>>t;
    k.insert(a);k.insert(b);k.insert(c);
    calc();
    assert(k.size()<10);
    pot={1};
    for(int i=0;i<300010;i++)pot.pb(pot.back()*p%mod);

    for(auto y:k){
        h.pb(vector<int> ());
        for(int i=0;i*dim<N;i++){
            string cur="";
            for(int j=dim*i;j<min(N,dim*(i+1));j++){
                cur+=y[j];
            }
            h.back().pb(hasha(cur));
            //cout<<"iniziali: "<<h.back().back()<<endl;
        }
    }
    for(int i=0;i*dim<N;i++){
        string cur="";
        for(int j=dim*i;j<min(N,dim*(i+1));j++){
            cur+=t[j];
        }
        tt.pb(hasha(cur));
    }
    //cout<<tt[0]<<" "<<hasha(t)<<endl;
    solve();
    for(int i=0;i<Q;i++){
        int x,y;
        char z;
        cin>>x>>y>>z;
        x--;y--;
        for(int j=x;j<=y/* && j%dim!=0*/;j++){
            int pp=j/dim;
            tt[pp]-=t[j]*pot[dim-j%dim-1];
            t[j]=z;
            tt[pp]+=z*pot[dim-j%dim-1];
            tt[pp]=(tt[pp]%mod+mod)%mod;
        }
        //cout<<tt[0]<<" "<<hasha(t)<<endl;
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:29:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i=0;i<v.size();i++)if(v[i]!=tt[i])ok=0;
      |                     ~^~~~~~~~~
Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:40:18: 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]
   40 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~

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