oj.uz

Submission #18864

# Submission time Handle Problem Language Result Execution time Memory
18864 2016-02-16T05:48:42 Z Namnamseo 구간 성분 (KOI15_interval) C++14
61 / 100
 847 ms 131072 KB 
#include <cstdio>
#include <set>
using namespace std;
struct tpl{
    int count[26];
    tpl operator-(const tpl& x) const {
        tpl ret;
        for(int i=0;i<26;++i) ret.count[i]=count[i]-x.count[i];
        return ret;
    }
    bool operator<(const tpl& x) const {
        for(int i=0;i<26;++i) if(count[i]!=x.count[i]) return count[i]<x.count[i];
        return false;
    }
    void operator=(const tpl& x){
        for(int i=0;i<26;++i) count[i]=x.count[i];
    }
};
set<tpl> s;
char da[1501];
char db[1501];
tpl ca[1501];
tpl cb[1501];
int n,m;
inline int max(int a,int b){ return a>b?a:b; }
inline int min(int a,int b){ return a>b?b:a; }
int main()
{
    scanf("%s%s",da+1,db+1);
    for(n=1;da[n];++n){
        ca[n]=ca[n-1];
        ++ca[n].count[da[n]-'a'];
    }
    for(m=1;db[m];++m){
        cb[m]=cb[m-1];
        ++cb[m].count[db[m]-'a'];
    }
    --n; --m;
    int len, maxlen = min(n,m);
    int i,j;
    tpl tmp;
    for(len=maxlen; len>=1; --len){
        for(i=len; i<=m; ++i){
            tmp=cb[i]-cb[i-len];
            s.insert(tmp);
        }
        for(i=len; i<=n; ++i){
            tmp=ca[i]-ca[i-len];
            if(s.find(tmp)!=s.end()){
                break;
            }
        }
        if(i<=n) break;
    }
    printf("%d\n",len);
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17492 KB Output is correct
2 Correct 41 ms 7592 KB Output is correct
3 Correct 0 ms 1520 KB Output is correct
4 Correct 0 ms 1520 KB Output is correct
5 Correct 88 ms 16964 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 64088 KB Output is correct
2 Correct 450 ms 68048 KB Output is correct
3 Correct 413 ms 67256 KB Output is correct
4 Correct 410 ms 65276 KB Output is correct
5 Correct 444 ms 67652 KB Output is correct
6 Correct 402 ms 65672 KB Output is correct
7 Correct 404 ms 67784 KB Output is correct
8 Correct 431 ms 67256 KB Output is correct
9 Correct 443 ms 67916 KB Output is correct
10 Correct 423 ms 67388 KB Output is correct

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 7988 KB Output is correct
2 Correct 847 ms 131012 KB Output is correct
3 Correct 759 ms 112004 KB Output is correct
4 Correct 26 ms 4424 KB Output is correct
5 Memory limit exceeded 739 ms 131072 KB Memory limit exceeded