oj.uz

Submission #18027

# Submission time Handle Problem Language Result Execution time Memory
18027 2016-01-18T12:39:42 Z gs14004 구간 성분 (KOI15_interval) C++14
100 / 100
 329 ms 1524 KB 
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long hsh;
const hsh mod1 = 1e9 + 513;
const hsh mod2 = 1e9 + 531;
 
int n, m;
char str1[1505], str2[1505];
int psum1[1505][26], psum2[1505][26];
 
vector<hsh> hs;
vector<hsh> hs2;
 
hsh make_hsh(int* a){
    hsh t1 = 0;
    for(int i=0; i<26; i++){
        t1 *= 1505ll;
        t1 += a[i];
    }
    return t1;
}
 
bool trial(int l){
    if(l == 0) return 1;
    hs.clear();
    for(int i=0; i<=n-l; i++){
        int hshOp[26] = {};
        for(int j=0; j<26; j++){
            hshOp[j] = psum1[i+l][j] - psum1[i][j];
        }
        hs.push_back(make_hsh(hshOp));
    }
    sort(hs.begin(), hs.end());
    for(int i=0; i<=m-l; i++){
        int hshOp[26] = {};
        for(int j=0; j<26; j++){
            hshOp[j] = psum2[i+l][j] - psum2[i][j];
        }
        hsh p = make_hsh(hshOp);
        if(*lower_bound(hs.begin(), hs.end(), p) == p) return 1;
    }
    return 0;
}
 
int main(){
    scanf("%s %s",str1+1,str2+1);
    n = (int)strlen(str1+1);
    m = (int)strlen(str2+1);
    for(int i=1; i<=n; i++){
        psum1[i][str1[i]-'a']++;
        for(int j=0; j<26; j++){
            psum1[i][j] += psum1[i-1][j];
        }
    }
    for(int i=1; i<=m; i++){
        psum2[i][str2[i]-'a']++;
        for(int j=0; j<26; j++){
            psum2[i][j] += psum2[i-1][j];
        }
    }
    int p = min(n, m);
    while(!trial(p)) p--;
    printf("%d",p);
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 1524 KB Output is correct
2 Correct 142 ms 1524 KB Output is correct
3 Correct 143 ms 1524 KB Output is correct
4 Correct 138 ms 1524 KB Output is correct
5 Correct 142 ms 1524 KB Output is correct
6 Correct 142 ms 1524 KB Output is correct
7 Correct 142 ms 1524 KB Output is correct
8 Correct 141 ms 1524 KB Output is correct
9 Correct 142 ms 1524 KB Output is correct
10 Correct 142 ms 1524 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1524 KB Output is correct
2 Correct 306 ms 1524 KB Output is correct
3 Correct 270 ms 1524 KB Output is correct
4 Correct 13 ms 1524 KB Output is correct
5 Correct 329 ms 1524 KB Output is correct