oj.uz

Submission #48942

# Submission time Handle Problem Language Result Execution time Memory
48942 2018-05-20T06:22:44 Z leehosu01 백신 (KOI13_vaccine) C++17
24 / 24
 32 ms 2848 KB 
#include<bits/stdc++.h>
using namespace std;
bitset<2500>ext;
bool phase=0;
typedef long long ll;
ll p1=10061,p2=100000007,n1=396,n2=117;
ll PW(ll X,ll Y,ll P)
{
    ll I=1ll<<62,cs=1;
    for(;I;I>>=1)
    {
        cs=cs*cs%P;
        if(I&Y)cs=cs*X%P;
    }
    return cs;
}
int N,K;
ll PS1,PS2;
vector<int>V;
struct C{
int H1,H2;
int from;
C RG(C&X)
{
    return {((H1-X.H1*PS1)%p1+p1)%p1,((H2-X.H2*PS2)%p2+p2)%p2};
}
bool operator<(const C&X)const{return H1==X.H1?H2<X.H2:H1<X.H1;}
bool operator==(const C&X)const{return H1==X.H1&&H2==X.H2;}
};
vector<C>VC,TV,TTV;
void BH(int n)
{
    int i;
    TV.resize(n+1);
    for(i=0;i<n;i++)
        TV[i+1]={(TV[i].H1*n1+V[i])%p1,(TV[i].H2*n2+V[i])%p2};
}
int in()
{
    int M;
    cin>>M;
    V.resize(M);
    for(int&I:V)cin>>I;
    return M;
}
void getH()
{
    TTV.clear();
    for(int i=K;i<=TV.size();i++)
    {
        TTV.push_back(TV[i].RG(TV[i-K]));
    }
}
void first()
{
    int L=in();
    BH(L);
    getH();
    VC.clear();
    VC.insert(VC.end(),TTV.begin(),TTV.end());
    sort(VC.begin(),VC.end());
    VC.resize(distance(VC.begin(),unique(VC.begin(),VC.end())) );
    for(auto&I:VC)I.from=(&I-&VC[0]);
}
void second()
{
    ext.reset();
    int L=in();
    BH(L);
    getH();
    for(auto&I:TTV)
    {
        if(I==*lower_bound(VC.begin(),VC.end(),I))
            ext[(*lower_bound(VC.begin(),VC.end(),I)).from]=1;
    }
    reverse(V.begin(), V.end());
    BH(L);
    getH();
    for(auto&I:TTV)
    {
        if(I==*lower_bound(VC.begin(),VC.end(),I))
            ext[(*lower_bound(VC.begin(),VC.end(),I)).from]=1;
    }
    int w=0;
    for(auto&I:VC)
    {
        if(ext[I.from])
            VC[w++]=I;
    }
    VC.resize(w);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>K;
    PS1=PW(n1,K,p1),PS2=PW(n2,K,p2);
    first();
    int i;
    for(i=1;i<N;i++)
        second();
    printf("%s",VC.empty()?  "NO":"YES");
}

Compilation message

vaccine.cpp: In member function 'C C::RG(C&)':
vaccine.cpp:25:34: warning: narrowing conversion of '((((((ll)((C*)this)->C::H1) - (((ll)X.C::H1) * PS1)) % p1) + p1) % p1)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
     return {((H1-X.H1*PS1)%p1+p1)%p1,((H2-X.H2*PS2)%p2+p2)%p2};
             ~~~~~~~~~~~~~~~~~~~~~^~~
vaccine.cpp:25:59: warning: narrowing conversion of '((((((ll)((C*)this)->C::H2) - (((ll)X.C::H2) * PS2)) % p2) + p2) % p2)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
     return {((H1-X.H1*PS1)%p1+p1)%p1,((H2-X.H2*PS2)%p2+p2)%p2};
                                      ~~~~~~~~~~~~~~~~~~~~~^~~
vaccine.cpp: In function 'void BH(int)':
vaccine.cpp:36:36: warning: narrowing conversion of '(((((ll)TV.std::vector<C>::operator[](((std::vector<C>::size_type)i)).C::H1) * n1) + ((ll)V.std::vector<int>::operator[](((std::vector<int>::size_type)i)))) % p1)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
         TV[i+1]={(TV[i].H1*n1+V[i])%p1,(TV[i].H2*n2+V[i])%p2};
                  ~~~~~~~~~~~~~~~~~~^~~
vaccine.cpp:36:58: warning: narrowing conversion of '(((((ll)TV.std::vector<C>::operator[](((std::vector<C>::size_type)i)).C::H2) * n2) + ((ll)V.std::vector<int>::operator[](((std::vector<int>::size_type)i)))) % p2)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
         TV[i+1]={(TV[i].H1*n1+V[i])%p1,(TV[i].H2*n2+V[i])%p2};
                                        ~~~~~~~~~~~~~~~~~~^~~
vaccine.cpp: In function 'void getH()':
vaccine.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=K;i<=TV.size();i++)
                 ~^~~~~~~~~~~

Subtask #1
2.64 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct

Subtask #2
3.12 / 3.12

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct

Subtask #3
3.6 / 3.6

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 2 ms 636 KB Output is correct
8 Correct 3 ms 636 KB Output is correct
9 Correct 4 ms 636 KB Output is correct
10 Correct 2 ms 636 KB Output is correct

Subtask #4
4.32 / 4.32

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 3 ms 636 KB Output is correct
3 Correct 4 ms 636 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 4 ms 636 KB Output is correct
7 Correct 3 ms 736 KB Output is correct
8 Correct 2 ms 740 KB Output is correct
9 Correct 3 ms 740 KB Output is correct
10 Correct 3 ms 740 KB Output is correct

Subtask #5
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 5 ms 740 KB Output is correct
2 Correct 7 ms 740 KB Output is correct
3 Correct 9 ms 740 KB Output is correct
4 Correct 22 ms 740 KB Output is correct
5 Correct 5 ms 740 KB Output is correct
6 Correct 6 ms 740 KB Output is correct
7 Correct 8 ms 944 KB Output is correct
8 Correct 12 ms 948 KB Output is correct
9 Correct 18 ms 948 KB Output is correct
10 Correct 16 ms 1252 KB Output is correct

Subtask #6
5.52 / 5.52

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1252 KB Output is correct
2 Correct 24 ms 1252 KB Output is correct
3 Correct 27 ms 1252 KB Output is correct
4 Correct 13 ms 1252 KB Output is correct
5 Correct 21 ms 1616 KB Output is correct
6 Correct 21 ms 1980 KB Output is correct
7 Correct 23 ms 2148 KB Output is correct
8 Correct 19 ms 2148 KB Output is correct
9 Correct 32 ms 2492 KB Output is correct
10 Correct 22 ms 2848 KB Output is correct