oj.uz

Submission #321245

# Submission time Handle Problem Language Result Execution time Memory
321245 2020-11-11T16:47:51 Z tjdgus4384 구간 성분 (KOI15_interval) C++14
100 / 100
 193 ms 492 KB 
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
long long p[30] = {614313243, 43029480, 52309234, 2347048024, 2345082354, 42039843, 70249523,123523561, 134141563, 273736614, 245774235, 945583495, 1509845718, 149315734, 1235751910, 132479822, 21234190349, 3241409824, 210497384, 1903784134, 17504353, 789845354, 39074583, 15790824, 143570154, 13475980452, 23470981234, 2019874312, 1908734134, 19378443};
long long p2[]={1553543355441,6835413543356,341238467843,5846878493734,255654493854,4385646055553,29333247254,56842665466513,6562454444132,33264680204,97185465094454,8937264644356,85143166465423,78565446465415,98746146556215,8547654654856,841537879874131,7293864657254,9814378779242,74464658844594,24495564314761,186549524066569,39665654465873,481654731322,41565458484,13646542908};

set<pair<long long, long long> > s;

int main(){
    cin >> s1 >> s2;
    for(int i = s1.size();i > 0;i--){
        if(i > s2.size()) continue;
        long long sum = 0, sum1 = 0;
        for(int j = 0;j < i;j++) {
            sum1 += p2[s1[j]-'a'];
            sum += p[s1[j]-'a'];
        }
        s.insert({sum, sum1});
        for(int j = i;j < s1.size();j++){
            sum -= p[s1[j-i]-'a'];
            sum += p[s1[j]-'a'];
            sum1 -= p2[s1[j-i]-'a'];
            sum1 += p2[s1[j]-'a'];
            s.insert({sum, sum1});
        }

        sum = 0, sum1 = 0;
        for(int j = 0;j < i;j++) {
            sum1 += p2[s2[j]-'a'];
            sum += p[s2[j]-'a'];
        }
        if(s.count({sum, sum1})) {printf("%d", i); return 0;}
        for(int j = i;j < s2.size();j++){
            sum -= p[s2[j-i]-'a'];
            sum += p[s2[j]-'a'];
            sum1 -= p2[s2[j-i]-'a'];
            sum1 += p2[s2[j]-'a'];
            if(s.count({sum, sum1})) {printf("%d", i); return 0;}
        }
        s.clear();
    }
    printf("0");
    return 0;
}

Compilation message

interval.cpp: In function 'int main()':
interval.cpp:12:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         if(i > s2.size()) continue;
      |            ~~^~~~~~~~~~~
interval.cpp:19:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for(int j = i;j < s1.size();j++){
      |                       ~~^~~~~~~~~~~
interval.cpp:33:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int j = i;j < s2.size();j++){
      |                       ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 364 KB Output is correct
2 Correct 12 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 21 ms 364 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 364 KB Output is correct
2 Correct 83 ms 492 KB Output is correct
3 Correct 86 ms 364 KB Output is correct
4 Correct 95 ms 364 KB Output is correct
5 Correct 85 ms 364 KB Output is correct
6 Correct 86 ms 364 KB Output is correct
7 Correct 79 ms 364 KB Output is correct
8 Correct 84 ms 364 KB Output is correct
9 Correct 83 ms 484 KB Output is correct
10 Correct 82 ms 364 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 364 KB Output is correct
2 Correct 182 ms 364 KB Output is correct
3 Correct 141 ms 364 KB Output is correct
4 Correct 6 ms 364 KB Output is correct
5 Correct 193 ms 364 KB Output is correct