oj.uz

Submission #558066

# Submission time Handle Problem Language Result Execution time Memory
558066 2022-05-06T16:45:00 Z groshi Crossing (JOI21_crossing) C++17
26 / 100
 257 ms 18252 KB 
#include<iostream>

using namespace std;
string s[10];
char jaki[4]={'J','O','I'};
long long pierw=1000696969;
long long pot[300000];
long long pref[300000];
long long hasze[300000];
long long drzewo[600000];
long long lazy[600000];
int n;
char brak(char a,char b)
{
    for(int i=0;i<3;i++)
        if(jaki[i]!=a && jaki[i]!=b)
            return jaki[i];
}
void comp(int co1,int co2,int gdzie)
{
    string pom="";
    for(int i=0;i<s[co1].length();i++)
    {
        if(s[co1][i]==s[co2][i])
            pom.push_back(s[co1][i]);
        else pom.push_back(brak(s[co1][i],s[co2][i]));
    }
    s[gdzie]=pom;
}
void zrob()
{
    comp(0,1,3);
    comp(0,2,4);
    comp(1,2,5);
    comp(3,2,6);
    comp(4,1,7);
    comp(0,5,8);
}
void pie()
{
    pot[0]=1;
    for(int i=1;i<=200000;i++)
        pot[i]=pot[i-1]*pierw;
    pref[0]=1;
    for(int i=1;i<=200000;i++)
        pref[i]=pref[i-1]+pot[i];
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<s[i].length();j++)
            hasze[i]=hasze[i]+(s[i][j]-'A'+1)*pot[j];
       //cout<<hasze[i]<<"\n";
    }
}
void prop(int x,int l,int r)
{
    if(lazy[x]==0)
        return;
    //cout<<pref[r-l]<<"\n";
    drzewo[x]=(pref[r-l]*lazy[x]);
    if(l!=r)
    {
        lazy[x*2]=lazy[x];
        lazy[x*2+1]=lazy[x];
    }
    lazy[x]=0;
}
void upd(int x,int l,int r,int x1,int y1,int co)
{
    //cout<<"jestem w "<<x<<"\n";
    prop(x,l,r);
    if(x1>r || y1<l || l>r)
        return;
    if(x1<=l && r<=y1)
    {
        lazy[x]=co;
        prop(x,l,r);
        return;
    }
    int mid=(l+r)/2;
    upd(x*2,l,mid,x1,y1,co);
    upd(x*2+1,mid+1,r,x1,y1,co);
    drzewo[x]=drzewo[x*2]+drzewo[x*2+1]*pot[mid-l+1];
}
long long idz()
{
    prop(1,1,n);
    return drzewo[1];
}
bool ok()
{
    long long hasz=idz();
    //cout<<hasz<<"\n";
    for(int i=0;i<9;i++)
        if(hasz==hasze[i])
            return 1;
    return 0;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    cin>>s[0]>>s[1]>>s[2];
    zrob();
    pie();
    int zap;
    cin>>zap;
    string wzor;
    cin>>wzor;
    for(int i=1;i<=wzor.length();i++)
        upd(1,1,n,i,i,wzor[i-1]-'A'+1);
    if(ok())
        cout<<"Yes\n";
    else cout<<"No\n";
    while(zap--)
    {
        int a,b;
        char c;
        cin>>a>>b>>c;
        upd(1,1,n,a,b,c-'A'+1);
        if(ok())
            cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void comp(int, int, int)':
Main.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<s[co1].length();i++)
      |                 ~^~~~~~~~~~~~~~~~
Main.cpp: In function 'void pie()':
Main.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=0;j<s[i].length();j++)
      |                     ~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=1;i<=wzor.length();i++)
      |                 ~^~~~~~~~~~~~~~~
Main.cpp: In function 'char brak(char, char)':
Main.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5432 KB Output is correct
2 Correct 75 ms 5556 KB Output is correct
3 Correct 72 ms 5452 KB Output is correct
4 Correct 64 ms 5432 KB Output is correct
5 Correct 60 ms 5452 KB Output is correct
6 Correct 61 ms 5472 KB Output is correct
7 Correct 61 ms 5452 KB Output is correct
8 Correct 68 ms 5512 KB Output is correct
9 Correct 72 ms 5584 KB Output is correct
10 Correct 69 ms 5612 KB Output is correct
11 Correct 68 ms 5580 KB Output is correct
12 Correct 68 ms 5600 KB Output is correct
13 Correct 65 ms 5576 KB Output is correct
14 Correct 71 ms 5556 KB Output is correct
15 Correct 67 ms 5504 KB Output is correct
16 Correct 67 ms 5592 KB Output is correct
17 Correct 64 ms 5508 KB Output is correct
18 Correct 68 ms 5472 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5432 KB Output is correct
2 Correct 75 ms 5556 KB Output is correct
3 Correct 72 ms 5452 KB Output is correct
4 Correct 64 ms 5432 KB Output is correct
5 Correct 60 ms 5452 KB Output is correct
6 Correct 61 ms 5472 KB Output is correct
7 Correct 61 ms 5452 KB Output is correct
8 Correct 68 ms 5512 KB Output is correct
9 Correct 72 ms 5584 KB Output is correct
10 Correct 69 ms 5612 KB Output is correct
11 Correct 68 ms 5580 KB Output is correct
12 Correct 68 ms 5600 KB Output is correct
13 Correct 65 ms 5576 KB Output is correct
14 Correct 71 ms 5556 KB Output is correct
15 Correct 67 ms 5504 KB Output is correct
16 Correct 67 ms 5592 KB Output is correct
17 Correct 64 ms 5508 KB Output is correct
18 Correct 68 ms 5472 KB Output is correct
19 Correct 249 ms 18252 KB Output is correct
20 Correct 227 ms 17228 KB Output is correct
21 Correct 198 ms 17848 KB Output is correct
22 Correct 177 ms 17440 KB Output is correct
23 Correct 102 ms 7076 KB Output is correct
24 Correct 101 ms 6948 KB Output is correct
25 Correct 216 ms 18144 KB Output is correct
26 Correct 257 ms 18244 KB Output is correct
27 Correct 205 ms 18252 KB Output is correct
28 Correct 211 ms 18072 KB Output is correct
29 Correct 191 ms 17952 KB Output is correct
30 Correct 114 ms 6984 KB Output is correct
31 Correct 198 ms 18192 KB Output is correct
32 Correct 190 ms 17800 KB Output is correct
33 Correct 115 ms 7000 KB Output is correct
34 Correct 209 ms 18048 KB Output is correct
35 Correct 172 ms 17060 KB Output is correct
36 Correct 99 ms 6952 KB Output is correct
37 Correct 102 ms 7052 KB Output is correct
38 Correct 216 ms 17104 KB Output is correct
39 Correct 166 ms 17132 KB Output is correct
40 Incorrect 165 ms 12996 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5432 KB Output is correct
2 Correct 75 ms 5556 KB Output is correct
3 Correct 72 ms 5452 KB Output is correct
4 Correct 64 ms 5432 KB Output is correct
5 Correct 60 ms 5452 KB Output is correct
6 Correct 61 ms 5472 KB Output is correct
7 Correct 61 ms 5452 KB Output is correct
8 Correct 68 ms 5512 KB Output is correct
9 Correct 72 ms 5584 KB Output is correct
10 Correct 69 ms 5612 KB Output is correct
11 Correct 68 ms 5580 KB Output is correct
12 Correct 68 ms 5600 KB Output is correct
13 Correct 65 ms 5576 KB Output is correct
14 Correct 71 ms 5556 KB Output is correct
15 Correct 67 ms 5504 KB Output is correct
16 Correct 67 ms 5592 KB Output is correct
17 Correct 64 ms 5508 KB Output is correct
18 Correct 68 ms 5472 KB Output is correct
19 Correct 69 ms 5480 KB Output is correct
20 Correct 71 ms 5452 KB Output is correct
21 Correct 67 ms 5564 KB Output is correct
22 Correct 59 ms 5364 KB Output is correct
23 Correct 70 ms 5484 KB Output is correct
24 Correct 64 ms 5508 KB Output is correct
25 Correct 64 ms 5540 KB Output is correct
26 Correct 62 ms 5452 KB Output is correct
27 Correct 72 ms 5492 KB Output is correct
28 Correct 61 ms 5336 KB Output is correct
29 Correct 68 ms 5568 KB Output is correct
30 Correct 59 ms 5324 KB Output is correct
31 Correct 66 ms 5604 KB Output is correct
32 Correct 64 ms 5512 KB Output is correct
33 Correct 66 ms 5580 KB Output is correct
34 Correct 59 ms 5392 KB Output is correct
35 Correct 66 ms 5592 KB Output is correct
36 Correct 71 ms 5572 KB Output is correct
37 Correct 64 ms 5540 KB Output is correct
38 Correct 65 ms 5500 KB Output is correct
39 Correct 63 ms 5568 KB Output is correct
40 Correct 64 ms 5580 KB Output is correct
41 Correct 70 ms 5584 KB Output is correct
42 Correct 76 ms 5540 KB Output is correct
43 Correct 62 ms 5536 KB Output is correct
44 Correct 66 ms 5648 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5432 KB Output is correct
2 Correct 75 ms 5556 KB Output is correct
3 Correct 72 ms 5452 KB Output is correct
4 Correct 64 ms 5432 KB Output is correct
5 Correct 60 ms 5452 KB Output is correct
6 Correct 61 ms 5472 KB Output is correct
7 Correct 61 ms 5452 KB Output is correct
8 Correct 68 ms 5512 KB Output is correct
9 Correct 72 ms 5584 KB Output is correct
10 Correct 69 ms 5612 KB Output is correct
11 Correct 68 ms 5580 KB Output is correct
12 Correct 68 ms 5600 KB Output is correct
13 Correct 65 ms 5576 KB Output is correct
14 Correct 71 ms 5556 KB Output is correct
15 Correct 67 ms 5504 KB Output is correct
16 Correct 67 ms 5592 KB Output is correct
17 Correct 64 ms 5508 KB Output is correct
18 Correct 68 ms 5472 KB Output is correct
19 Correct 249 ms 18252 KB Output is correct
20 Correct 227 ms 17228 KB Output is correct
21 Correct 198 ms 17848 KB Output is correct
22 Correct 177 ms 17440 KB Output is correct
23 Correct 102 ms 7076 KB Output is correct
24 Correct 101 ms 6948 KB Output is correct
25 Correct 216 ms 18144 KB Output is correct
26 Correct 257 ms 18244 KB Output is correct
27 Correct 205 ms 18252 KB Output is correct
28 Correct 211 ms 18072 KB Output is correct
29 Correct 191 ms 17952 KB Output is correct
30 Correct 114 ms 6984 KB Output is correct
31 Correct 198 ms 18192 KB Output is correct
32 Correct 190 ms 17800 KB Output is correct
33 Correct 115 ms 7000 KB Output is correct
34 Correct 209 ms 18048 KB Output is correct
35 Correct 172 ms 17060 KB Output is correct
36 Correct 99 ms 6952 KB Output is correct
37 Correct 102 ms 7052 KB Output is correct
38 Correct 216 ms 17104 KB Output is correct
39 Correct 166 ms 17132 KB Output is correct
40 Incorrect 165 ms 12996 KB Output isn't correct
41 Halted 0 ms 0 KB -