oj.uz

Submission #20223

# Submission time Handle Problem Language Result Execution time Memory
20223 2016-04-20T16:00:01 Z ansol4328 구간 성분 (KOI15_interval) C++
30 / 100
 1078 ms 9 KB 
#include<stdio.h>
#include<string.h>
#include<vector>

#define Mod1 10007

using namespace std;

struct A
{
    int st, fn;
};

vector<A> hash_table1[Mod1+2];
A in;
char a[1502], b[1502];

bool compair1(int key, int s, int f)
{
    int i, j, len=f-s+1, n=hash_table1[key].size();
    int cnta[30]={0,}, cntb[30]={0,}, ss, ff;
 
    for(i=s ; i<=f ; i++) cntb[b[i]-'a'+1]++;
    for(i=0 ; i<n ; i++)
    {
        ff=hash_table1[key][i].fn, ss=hash_table1[key][i].st;
        if(ff-ss+1==len)
        {
            for(j=ss ; j<=ff ; j++) cnta[a[j]-'a'+1]++;
            for(j=1 ; j<=26 ; j++) if(cnta[j]!=cntb[j]) break;
            if(j>26) break;
        }
        for(j=1 ; j<=26 ; j++) cnta[j]=0;
    }
    if(i<n) return true;
    else return false;
}

int main()
{
    int la, lb, i, j;
    int sum1, out=0;
    bool tf1;

    scanf("%s %s",a,b);
    la=strlen(a), lb=strlen(b);
    for(i=0 ; i<la ; i++)
    {
        sum1=0;
        for(j=i ; j<la ; j++)
        {
            sum1+=(a[j]-'a'+1);
            sum1%=Mod1;
            in.st=i, in.fn=j;
            hash_table1[sum1].push_back(in);
        }
    }
    for(i=0 ; i<lb ; i++)
    {
        sum1=0;
        for(j=i ; j<lb ; j++)
        {
            sum1+=(b[j]-'a'+1);
            sum1%=Mod1;
            tf1=compair1(sum1,i,j);
            if(tf1 && out<j-i+1) out=j-i+1;
        }
    }
    printf("%d",out);
    return 0;
}

Compilation message

interval.cpp: In function 'int main()':
interval.cpp:45:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s %s",a,b);
                       ^

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1 KB Output is correct
2 Correct 182 ms 2 KB Output is correct
3 Correct 219 ms 2 KB Output is correct
4 Correct 122 ms 2 KB Output is correct
5 Correct 172 ms 2 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 6 KB Time limit exceeded

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 9 KB Time limit exceeded