oj.uz

Submission #26679

# Submission time Handle Problem Language Result Execution time Memory
26679 2017-07-04T16:30:40 Z TAMREF 구간 성분 (KOI15_interval) C++11
7 / 100
 283 ms 2160 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1610612741;
ll pow1500[26]={1};
char A[1505], B[1505];
int N,M;
set<ll> S;
void init(){
    for(int i=1;i<26;i++) pow1500[i]=(pow1500[i-1]*26)%mod;
    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]&=15;
    for(int i=0;i<M;i++) B[i]&=15;
}
bool pro(int x){
    S.clear();
    ll H=0;
    for(int i=0;i<x;i++) H=(H+pow1500[A[i]-1])%mod;
    S.insert(H);
    for(int i=x;i<N;i++){
        H=(((H+pow1500[A[i]-1])%mod-pow1500[A[i-x]-1])%mod+mod)%mod;
        S.insert(H);
    }
    H=0;
    for(int i=0;i<x;i++) H=(H+pow1500[B[i]-1])%mod;
    if(S.find(H)!=S.end()) return true;
    for(int i=x;i<M;i++){
        H=(((H+pow1500[B[i]-1])%mod-pow1500[B[i-x]-1])%mod+mod)%mod;
        if(S.find(H)!=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 'void init()':
interval.cpp:11: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:12: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

# Verdict Execution time Memory 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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2028 KB Output is correct
2 Incorrect 119 ms 2028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2028 KB Output is correct
2 Correct 283 ms 2160 KB Output is correct
3 Correct 259 ms 2160 KB Output is correct
4 Incorrect 109 ms 2028 KB Output isn't correct
5 Halted 0 ms 0 KB -