oj.uz

Submission #134258

# Submission time Handle Problem Language Result Execution time Memory
134258 2019-07-22T09:55:33 Z ansol4328 구간 성분 (KOI15_interval) C++11
100 / 100
 267 ms 632 KB 
#include<stdio.h>
#include<string.h>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
typedef long long ll;
typedef pair<ll,int> P;

int n, m;
char s1[1505], s2[1505];
ll eval[30];
const ll MOD=1e9+7, e=1501;

void Hashing(int len, vector<P> &lst)
{
    ll val=0;
    for(int i=1 ; i<=len ; i++) (val+=eval[s1[i]-'a'])%=MOD;
    lst.push_back(P(val,1));
    for(int i=len+1 ; i<=n ; i++)
    {
        val=(val-eval[s1[i-len]-'a']+MOD)%MOD;
        (val+=eval[s1[i]-'a'])%=MOD;
        lst.push_back(P(val,i-len+1));
    }
    sort(lst.begin(),lst.end());
}

int get_st(ll val, vector<P> &lst)
{
    int st=0, fn=lst.size()-1, mid, idx=-1;
    while(st<=fn)
    {
        mid=(st+fn)>>1;
        if(lst[mid].first<val) st=mid+1;
        else fn=mid-1, idx=mid;
    }
    if(idx==-1 || lst[idx].first!=val) return -1;
    return idx;
}

int get_fn(ll val, vector<P> &lst)
{
    int st=0, fn=lst.size()-1, mid, idx=-1;
    while(st<=fn)
    {
        mid=(st+fn)>>1;
        if(lst[mid].first>val) fn=mid-1;
        else st=mid+1, idx=mid;
    }
    if(idx==-1 || lst[idx].first!=val) return -1;
    return idx;
}

bool correct(int st1, int st2, int len)
{
    int cnt1[30]={0,};
    int cnt2[30]={0,};
    for(int i=st1 ; i<st1+len ; i++) cnt1[s1[i]-'a']++;
    for(int i=st2 ; i<st2+len ; i++) cnt2[s2[i]-'a']++;
    for(int i=0 ; i<26 ; i++) if(cnt1[i]!=cnt2[i]) return false;
    return true;
}

bool Matching(int len, vector<P> &lst)
{
    ll val=0;
    for(int i=1 ; i<=len ; i++) (val+=eval[s2[i]-'a'])%=MOD;
    int s=get_st(val,lst);
    int f=get_fn(val,lst);
    if(s!=-1 && f!=-1)
    {
        for(int i=s ; i<=f ; i++)
        {
            if(correct(lst[i].second,1,len)) return true;
        }
    }
    for(int i=len+1 ; i<=m ; i++)
    {
        val=(val-eval[s2[i-len]-'a']+MOD)%MOD;
        (val+=eval[s2[i]-'a'])%=MOD;
        s=get_st(val,lst);
        f=get_fn(val,lst);
        if(s!=-1 && f!=-1)
        {
            for(int j=s ; j<=f ; j++)
            {
                if(correct(lst[j].second,i-len+1,len)) return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%s",&s1[1]);
    scanf("%s",&s2[1]);
    n=strlen(&s1[1]), m=strlen(&s2[1]);
    eval[0]=1;
    for(int i=1 ; i<26 ; i++) eval[i]=(eval[i-1]*e)%MOD;
    for(int i=min(n,m) ; i>0 ; i--)
    {
        vector<P> lst;
        Hashing(i,lst);
        if(Matching(i,lst))
        {
            printf("%d",i);
            return 0;
        }
    }
    printf("0");
    return 0;
}

Compilation message

interval.cpp: In function 'int main()':
interval.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",&s1[1]);
     ~~~~~^~~~~~~~~~~~~
interval.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",&s2[1]);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 348 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 14 ms 632 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 25 ms 256 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 536 KB Output is correct
2 Correct 114 ms 388 KB Output is correct
3 Correct 113 ms 376 KB Output is correct
4 Correct 112 ms 392 KB Output is correct
5 Correct 113 ms 384 KB Output is correct
6 Correct 112 ms 396 KB Output is correct
7 Correct 112 ms 392 KB Output is correct
8 Correct 111 ms 376 KB Output is correct
9 Correct 112 ms 376 KB Output is correct
10 Correct 113 ms 492 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 376 KB Output is correct
2 Correct 264 ms 512 KB Output is correct
3 Correct 209 ms 416 KB Output is correct
4 Correct 16 ms 372 KB Output is correct
5 Correct 267 ms 420 KB Output is correct