QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557588#8668. 回文路径fairyqq280 43ms9772kbC++141.8kb2024-09-11 10:23:372024-09-11 10:23:39

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 10:23:39]
  • 评测
  • 测评结果:0
  • 用时:43ms
  • 内存:9772kb
  • [2024-09-11 10:23:37]
  • 提交

answer

#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cassert>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 200100;
const ll base = 26, mod = 1000000007;
int n, ans, f[N]; 
ll pw[N], h[N], g[N];
ll qry(ll *h, int x, int y){
    return ((h[y] - h[x-1] * pw[y-x+1])%mod+mod)%mod;
}

void solve(char *s, char *t){
    rep(i, 1, n) h[i] = (h[i-1] * base + s[i] - 'a') % mod;
    per(i, n, 1) g[i] = (g[i+1] * base + t[i] - 'a') % mod;
    reverse(g+1, g+n+1);
    // rep(i, 1, n) putchar(s[i]);
    // putchar('\n');
    // rep(i, 1, n) putchar(t[i]);
    // putchar('\n');
    for(int i = 1, r = 0, mid = 0; i <= n; i++){
		if(i <= r) f[i] = min(f[mid * 2 - i], r - i + 1);
		while(s[i - f[i]] == s[i + f[i]]) f[i]++;
		if(f[i] + i - 1 >= r) r = f[i] + i - 1, mid = i;
    }
    rep(i, 1, n){
        ans = max(ans, f[i]-1);
        int l = f[i], r = min(n-i+2, i-1);
        while(l <= r){
            int mid = (l+r)>>1;
            if(qry(h, i-mid, i-f[i]) == qry(g, n-i-mid+3, n-i-f[i]+3)) ans = max(ans, mid), l = mid + 1;
            else r = mid - 1;
        }
    }
}

char s[N], t[N];
int main(){
    pw[0] = 1; rep(i, 1, N-5) pw[i] = pw[i-1] * base % mod;
    scanf("%d", &n); 
    s[0] = '$', s[1] = '#', t[0] = '$', t[1] = '#';
    rep(i, 1, n){
        char c = getchar(); while(!islower(c)) c = getchar();
        s[i<<1] = c, s[i<<1|1] = '#';
    }
    rep(i, 1, n){
        char c = getchar(); while(!islower(c)) c = getchar();
        t[i<<1] = c, t[i<<1|1] = '#';
    }
    n = n<<1|1;
    s[n+1] = '^', t[n+1] = '^';
    solve(s, t);
    reverse(s, s+n+2); reverse(t, t+n+2);
    solve(t, s);
    printf("%d\n", ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 8788kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

9

result:

wrong answer 1st lines differ - expected: '6', found: '9'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 43ms
memory: 9772kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

11

result:

wrong answer 1st lines differ - expected: '9', found: '11'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%