oj.uz

Submission #18865

# Submission time Handle Problem Language Result Execution time Memory
18865 2016-02-16T05:49:39 Z Namnamseo 구간 성분 (KOI15_interval) C++14
100 / 100
 516 ms 1500 KB 
#include <cstdio>
#include <set>
using namespace std;
struct tpl{
    short 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;
      s.clear();
    }
    printf("%d\n",len);
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 1368 KB Output is correct
2 Correct 225 ms 1368 KB Output is correct
3 Correct 219 ms 1368 KB Output is correct
4 Correct 215 ms 1368 KB Output is correct
5 Correct 214 ms 1368 KB Output is correct
6 Correct 208 ms 1368 KB Output is correct
7 Correct 219 ms 1368 KB Output is correct
8 Correct 218 ms 1368 KB Output is correct
9 Correct 221 ms 1368 KB Output is correct
10 Correct 222 ms 1368 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1368 KB Output is correct
2 Correct 420 ms 1368 KB Output is correct
3 Correct 368 ms 1368 KB Output is correct
4 Correct 16 ms 1368 KB Output is correct
5 Correct 516 ms 1500 KB Output is correct