oj.uz

Submission #419985

# Submission time Handle Problem Language Result Execution time Memory
419985 2021-06-07T21:01:11 Z davi_bart Crossing (JOI21_crossing) C++17
26 / 100
 3391 ms 6624 KB 
#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;
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;

        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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 5444 KB Output is correct
2 Correct 558 ms 5444 KB Output is correct
3 Correct 611 ms 5444 KB Output is correct
4 Correct 517 ms 5444 KB Output is correct
5 Correct 488 ms 5444 KB Output is correct
6 Correct 516 ms 5444 KB Output is correct
7 Correct 415 ms 5444 KB Output is correct
8 Correct 598 ms 5444 KB Output is correct
9 Correct 545 ms 5444 KB Output is correct
10 Correct 546 ms 5444 KB Output is correct
11 Correct 553 ms 5444 KB Output is correct
12 Correct 546 ms 5572 KB Output is correct
13 Correct 546 ms 5572 KB Output is correct
14 Correct 557 ms 5444 KB Output is correct
15 Correct 542 ms 5440 KB Output is correct
16 Correct 554 ms 5444 KB Output is correct
17 Correct 539 ms 5444 KB Output is correct
18 Correct 581 ms 5444 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 5444 KB Output is correct
2 Correct 558 ms 5444 KB Output is correct
3 Correct 611 ms 5444 KB Output is correct
4 Correct 517 ms 5444 KB Output is correct
5 Correct 488 ms 5444 KB Output is correct
6 Correct 516 ms 5444 KB Output is correct
7 Correct 415 ms 5444 KB Output is correct
8 Correct 598 ms 5444 KB Output is correct
9 Correct 545 ms 5444 KB Output is correct
10 Correct 546 ms 5444 KB Output is correct
11 Correct 553 ms 5444 KB Output is correct
12 Correct 546 ms 5572 KB Output is correct
13 Correct 546 ms 5572 KB Output is correct
14 Correct 557 ms 5444 KB Output is correct
15 Correct 542 ms 5440 KB Output is correct
16 Correct 554 ms 5444 KB Output is correct
17 Correct 539 ms 5444 KB Output is correct
18 Correct 581 ms 5444 KB Output is correct
19 Correct 1443 ms 6624 KB Output is correct
20 Correct 3391 ms 6608 KB Output is correct
21 Incorrect 1033 ms 6588 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 5444 KB Output is correct
2 Correct 558 ms 5444 KB Output is correct
3 Correct 611 ms 5444 KB Output is correct
4 Correct 517 ms 5444 KB Output is correct
5 Correct 488 ms 5444 KB Output is correct
6 Correct 516 ms 5444 KB Output is correct
7 Correct 415 ms 5444 KB Output is correct
8 Correct 598 ms 5444 KB Output is correct
9 Correct 545 ms 5444 KB Output is correct
10 Correct 546 ms 5444 KB Output is correct
11 Correct 553 ms 5444 KB Output is correct
12 Correct 546 ms 5572 KB Output is correct
13 Correct 546 ms 5572 KB Output is correct
14 Correct 557 ms 5444 KB Output is correct
15 Correct 542 ms 5440 KB Output is correct
16 Correct 554 ms 5444 KB Output is correct
17 Correct 539 ms 5444 KB Output is correct
18 Correct 581 ms 5444 KB Output is correct
19 Correct 568 ms 5568 KB Output is correct
20 Correct 619 ms 5440 KB Output is correct
21 Correct 558 ms 5444 KB Output is correct
22 Correct 373 ms 5444 KB Output is correct
23 Correct 561 ms 5444 KB Output is correct
24 Correct 493 ms 5444 KB Output is correct
25 Correct 560 ms 5444 KB Output is correct
26 Correct 409 ms 5444 KB Output is correct
27 Correct 566 ms 5444 KB Output is correct
28 Correct 485 ms 5444 KB Output is correct
29 Correct 578 ms 5444 KB Output is correct
30 Correct 375 ms 5444 KB Output is correct
31 Correct 642 ms 5568 KB Output is correct
32 Correct 568 ms 5440 KB Output is correct
33 Correct 606 ms 5440 KB Output is correct
34 Correct 432 ms 5440 KB Output is correct
35 Correct 649 ms 5544 KB Output is correct
36 Correct 624 ms 5560 KB Output is correct
37 Correct 647 ms 5532 KB Output is correct
38 Correct 585 ms 5440 KB Output is correct
39 Correct 590 ms 5440 KB Output is correct
40 Correct 587 ms 5440 KB Output is correct
41 Correct 600 ms 5512 KB Output is correct
42 Correct 598 ms 5440 KB Output is correct
43 Correct 477 ms 5440 KB Output is correct
44 Correct 587 ms 5540 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 5444 KB Output is correct
2 Correct 558 ms 5444 KB Output is correct
3 Correct 611 ms 5444 KB Output is correct
4 Correct 517 ms 5444 KB Output is correct
5 Correct 488 ms 5444 KB Output is correct
6 Correct 516 ms 5444 KB Output is correct
7 Correct 415 ms 5444 KB Output is correct
8 Correct 598 ms 5444 KB Output is correct
9 Correct 545 ms 5444 KB Output is correct
10 Correct 546 ms 5444 KB Output is correct
11 Correct 553 ms 5444 KB Output is correct
12 Correct 546 ms 5572 KB Output is correct
13 Correct 546 ms 5572 KB Output is correct
14 Correct 557 ms 5444 KB Output is correct
15 Correct 542 ms 5440 KB Output is correct
16 Correct 554 ms 5444 KB Output is correct
17 Correct 539 ms 5444 KB Output is correct
18 Correct 581 ms 5444 KB Output is correct
19 Correct 1443 ms 6624 KB Output is correct
20 Correct 3391 ms 6608 KB Output is correct
21 Incorrect 1033 ms 6588 KB Output isn't correct
22 Halted 0 ms 0 KB -