Submission #419991

#	Time	Username	Problem	Language	Result	Execution time	Memory
419991		davi_bart	Crossing (JOI21_crossing)	C++17	100 / 100	4321 ms	8832 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=200;
const int p=257,mod=1e9+9;
vector<int> pot;
vector<int> tt;
map<char,int> val;
vector<char> qq(1000010,'x');
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);

    val['I']=hasha(string(dim,'I'));
    val['J']=hasha(string(dim,'J'));
    val['O']=hasha(string(dim,'O'));

    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--;
        int pos=x-x%dim;
        for(int j=pos;j<min(N,pos+dim);j++){
            int pp=j/dim;
            if(qq[pp]!='x')t[j]=qq[pp];

            tt[pp]-=t[j]*pot[dim-j%dim-1];
            if(j>=x && j<=y)t[j]=z;
            tt[pp]+=t[j]*pot[dim-j%dim-1];
            tt[pp]=(tt[pp]%mod+mod)%mod;
        }
        qq[pos/dim]='x';

        x=x-x%dim+dim;

        pos=y-y%dim;
        for(int j=pos;j<min(N,pos+dim);j++){
            int pp=j/dim;
            if(qq[pp]!='x')t[j]=qq[pp];

            tt[pp]-=t[j]*pot[dim-j%dim-1];
            if(j>=x && j<=y)t[j]=z;
            tt[pp]+=t[j]*pot[dim-j%dim-1];
            tt[pp]=(tt[pp]%mod+mod)%mod;
        }
        y=y-y%dim;
        qq[pos/dim]='x';

        for(int j=x;j<y;j+=dim){
            int pp=j/dim;
            tt[pp]=val[z];
            qq[pp]=z;
        }

        //cout<<tt[0]<<" "<<hasha(t)<<endl;
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:31: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]
   31 |         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:42: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]
   42 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~

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