oj.uz

답안 #26683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26683 2017-07-04T16:43:26 Z TAMREF 구간 성분 (KOI15_interval) C++11
100 / 100
 316 ms 2160 KB 
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
const ll mod[2]={1000000007,1610612741};
ll pow1500[2][26]={{1},{1}};
char A[1505], B[1505];
int N,M;
set<pair<ll,ll>> S;
void init(){
    for(int i=1;i<26;i++) for(int b=0;b<2;b++) pow1500[b][i]=(pow1500[b][i-1]*1500)%mod[b];
    fgets(A,1502,stdin); N=strlen(A); A[--N]=0;
    fgets(B,1502,stdin); M=strlen(B); B[--M]=0;
    for(int i=0;i<N;i++) A[i]-='a';
    for(int i=0;i<M;i++) B[i]-='a';
}
bool pro(int x){
    S.clear();
    ll H[2]={0,0};
    for(int i=0;i<x;i++)for(int b=0;b<2;b++) H[b]=(H[b]+pow1500[b][A[i]])%mod[b];
    S.insert(mp(H[0],H[1]));
    for(int i=x;i<N;i++){
        for(int b=0;b<2;b++)
            H[b]=(((H[b]+pow1500[b][A[i]])%mod[b]-pow1500[b][A[i-x]])%mod[b]+mod[b])%mod[b];
        S.insert(mp(H[0],H[1]));
    }
    H[0]=H[1]=0;
    for(int i=0;i<x;i++) for(int b=0;b<2;b++) H[b]=(H[b]+pow1500[b][B[i]])%mod[b];
    if(S.find(mp(H[0],H[1]))!=S.end()) return true;
    for(int i=x;i<M;i++){
        for(int b=0;b<2;b++)
            H[b]=(((H[b]+pow1500[b][B[i]])%mod[b]-pow1500[b][B[i-x]])%mod[b]+mod[b])%mod[b];
        if(S.find(mp(H[0],H[1]))!=S.end()) return true;
    }
    return false;
}
int main(){
    init();
    int ans=0, x=min(N,M);
    for(int i=1;i<=x;i++) if(pro(i)) ans=max(ans,i);
    printf("%d\n",ans);
}

Compilation message

interval.cpp: In function 'bool pro(int)':
interval.cpp:20:72: warning: array subscript has type 'char' [-Wchar-subscripts]
     for(int i=0;i<x;i++)for(int b=0;b<2;b++) H[b]=(H[b]+pow1500[b][A[i]])%mod[b];
                                                                        ^
interval.cpp:24:41: warning: array subscript has type 'char' [-Wchar-subscripts]
             H[b]=(((H[b]+pow1500[b][A[i]])%mod[b]-pow1500[b][A[i-x]])%mod[b]+mod[b])%mod[b];
                                         ^
interval.cpp:24:68: warning: array subscript has type 'char' [-Wchar-subscripts]
             H[b]=(((H[b]+pow1500[b][A[i]])%mod[b]-pow1500[b][A[i-x]])%mod[b]+mod[b])%mod[b];
                                                                    ^
interval.cpp:28:73: warning: array subscript has type 'char' [-Wchar-subscripts]
     for(int i=0;i<x;i++) for(int b=0;b<2;b++) H[b]=(H[b]+pow1500[b][B[i]])%mod[b];
                                                                         ^
interval.cpp:32:41: warning: array subscript has type 'char' [-Wchar-subscripts]
             H[b]=(((H[b]+pow1500[b][B[i]])%mod[b]-pow1500[b][B[i-x]])%mod[b]+mod[b])%mod[b];
                                         ^
interval.cpp:32:68: warning: array subscript has type 'char' [-Wchar-subscripts]
             H[b]=(((H[b]+pow1500[b][B[i]])%mod[b]-pow1500[b][B[i-x]])%mod[b]+mod[b])%mod[b];
                                                                    ^
interval.cpp: In function 'void init()':
interval.cpp:12:24: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets(A,1502,stdin); N=strlen(A); A[--N]=0;
                        ^
interval.cpp:13:24: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets(B,1502,stdin); M=strlen(B); B[--M]=0;
                        ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2028 KB Output is correct
4 Correct 0 ms 2028 KB Output is correct
5 Correct 0 ms 2028 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 2028 KB Output is correct
2 Correct 23 ms 2028 KB Output is correct
3 Correct 6 ms 2028 KB Output is correct
4 Correct 3 ms 2028 KB Output is correct
5 Correct 29 ms 2028 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 2160 KB Output is correct
2 Correct 139 ms 2160 KB Output is correct
3 Correct 126 ms 2160 KB Output is correct
4 Correct 123 ms 2160 KB Output is correct
5 Correct 123 ms 2160 KB Output is correct
6 Correct 123 ms 2160 KB Output is correct
7 Correct 129 ms 2160 KB Output is correct
8 Correct 129 ms 2160 KB Output is correct
9 Correct 133 ms 2160 KB Output is correct
10 Correct 129 ms 2160 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 2028 KB Output is correct
2 Correct 296 ms 2160 KB Output is correct
3 Correct 279 ms 2160 KB Output is correct
4 Correct 109 ms 2028 KB Output is correct
5 Correct 316 ms 2160 KB Output is correct