oj.uz

답안 #18024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18024 2016-01-18T11:33:14 Z gs13068 구간 성분 (KOI15_interval) C++
100 / 100
 384 ms 18448 KB 
#include<cstdio>
#include<cstring>
#include<algorithm>
 
const int mod1 = 1000000007, mod2 = 1000000009;
 
char a[2222],b[2222];
 
std::pair<int,int> d[2222222];
int dn;
 
std::pair<int,int> p[33];
 
int isprime(int x)
{
    int i;
    for(i=2;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}
 
int main()
{
    std::pair<int,int> P;
    int i,j,n,m,r=0;
    scanf("%s%s",a,b);
    n=strlen(a);m=strlen(b);
    p[0].first=p[0].second=1;
    for(i=1;i<26;i++)
    {
        p[i].first=2003LL*p[i-1].first%mod1;
        p[i].second=2003LL*p[i-1].second%mod2;
    }
    for(i=0;i<n;i++)
    {
        P.first=P.second=0;
        for(j=i;j<n;j++)
        {
            P.first=(P.first+p[a[j]-97].first)%mod1;
            P.second=(P.second+p[a[j]-97].second)%mod2;
            d[dn++]=P;
        }
    }
    std::sort(d,d+dn);
    for(i=0;i<m;i++)
    {
        P.first=P.second=0;
        for(j=i;j<m;j++)
        {
            P.first=(P.first+p[b[j]-97].first)%mod1;
            P.second=(P.second+p[b[j]-97].second)%mod2;
            if(std::binary_search(d,d+dn,P))r=std::max(r,j-i+1);
        }
    }
    printf("%d\n",r);
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 18448 KB Output is correct
2 Correct 0 ms 18448 KB Output is correct
3 Correct 3 ms 18448 KB Output is correct
4 Correct 3 ms 18448 KB Output is correct
5 Correct 0 ms 18448 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 18448 KB Output is correct
2 Correct 25 ms 18448 KB Output is correct
3 Correct 26 ms 18448 KB Output is correct
4 Correct 27 ms 18448 KB Output is correct
5 Correct 35 ms 18448 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 18448 KB Output is correct
2 Correct 163 ms 18448 KB Output is correct
3 Correct 155 ms 18448 KB Output is correct
4 Correct 162 ms 18448 KB Output is correct
5 Correct 165 ms 18448 KB Output is correct
6 Correct 156 ms 18448 KB Output is correct
7 Correct 156 ms 18448 KB Output is correct
8 Correct 158 ms 18448 KB Output is correct
9 Correct 160 ms 18448 KB Output is correct
10 Correct 160 ms 18448 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 18448 KB Output is correct
2 Correct 369 ms 18448 KB Output is correct
3 Correct 363 ms 18448 KB Output is correct
4 Correct 287 ms 18448 KB Output is correct
5 Correct 384 ms 18448 KB Output is correct