QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557527 | #8668. 回文路径 | fairyqq28 | 20 | 41ms | 9772kb | C++14 | 1.8kb | 2024-09-11 10:10:03 | 2024-09-11 10:10:04 |
Judging History
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 = 998244353;
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;
solve(s, t);
reverse(s, s+n+1); reverse(t, t+n+1);
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: 0ms
memory: 8996kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
7
result:
wrong answer 1st lines differ - expected: '6', found: '7'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 41ms
memory: 9632kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 40ms
memory: 9712kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 40ms
memory: 9632kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 41ms
memory: 9772kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 26ms
memory: 9696kb
input:
99999 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok single line: '99999'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%