Task: | Longest palindrome |
Sender: | aalto2024j_005 |
Submission time: | 2024-11-06 16:21:19 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.01 s | details |
#2 | ACCEPTED | 0.01 s | details |
#3 | ACCEPTED | 0.46 s | details |
#4 | ACCEPTED | 0.60 s | details |
#5 | ACCEPTED | 0.71 s | details |
#6 | ACCEPTED | 0.71 s | details |
#7 | ACCEPTED | 0.71 s | details |
#8 | ACCEPTED | 0.71 s | details |
#9 | ACCEPTED | 0.01 s | details |
#10 | ACCEPTED | 0.01 s | details |
#11 | ACCEPTED | 0.17 s | details |
#12 | ACCEPTED | 0.01 s | details |
#13 | ACCEPTED | 0.01 s | details |
#14 | ACCEPTED | 0.01 s | details |
#15 | ACCEPTED | 0.01 s | details |
#16 | ACCEPTED | 0.23 s | details |
Code
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i=a;i<(b);++i) #define all(x) begin(x),end(x) #define sz(x) int((x).size()) using ll = long long; using pii = pair<int,int>; using vi = vector<int>; const int A = 911382323; const int B = 972663749; const int N = 1e6; int P[N]; vi hh(const string& a) { vi h(sz(a)); h[0] = a[0]; rep(i,1,sz(a)) { h[i] = (h[i-1]*ll(A) + a[i]) % B; } return h; } int hget(const vi& h, int a, int b) { if (a == 0) return h[b]; int r = (h[b] - h[a-1]*ll(P[b-a+1])) % B; return r < 0 ? r + B : r; } int hcomp(const vi& a, const vi& b, const string& as, const string& bs) { int i = -1; int n = min(sz(a),sz(b)); for (int s = 1<<20; s >= 1; s /= 2) { i += s; if (i >= n || a[i] != b[i]) i -= s; } return i == n ? sz(a) - sz(b) : as[i+1] - bs[i+1]; } bool isPalidrom(const vi& s, const vi& rs, int a, int b) { return hget(s,a,b) == hget(rs,sz(rs)-1-b,sz(rs)-1-a); } int main() { P[0] = 1; rep(i,1,N) P[i] = ll(A) * P[i-1] % B; string a; cin >> a; int n = sz(a); vi h = hh(a); reverse(all(a)); vi rh = hh(a); int ans = 0, anss = 0; rep(i,0,n) { int j = 0; for (int s = 1<<20; s >= 1; s /= 2) { j += s; if (i+j >= n || i-j < 0 || !isPalidrom(h,rh,i-j,i+j)) j -= s; } if (j*2+1 > anss) { ans = i-j; anss = j*2+1; } j = -1; for (int s = 1<<20; s >= 1; s /= 2) { j += s; if (i+j+1 >= n || i-j < 0 || !isPalidrom(h,rh,i-j,i+j+1)) j -= s; } if (j*2+2 > anss) { ans = i-j; anss = j*2+2; } } reverse(all(a)); cout << string_view(a).substr(ans,anss); }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
aaaaaaaaaa |
correct output |
---|
aaaaaaaaaa |
user output |
---|
aaaaaaaaaa |
Test 2
Verdict: ACCEPTED
input |
---|
ababababab |
correct output |
---|
ababababa |
user output |
---|
ababababa |
Test 3
Verdict: ACCEPTED
input |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
correct output |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
user output |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
Test 4
Verdict: ACCEPTED
input |
---|
ababababababababababababababab... |
correct output |
---|
ababababababababababababababab... |
user output |
---|
ababababababababababababababab... |
Test 5
Verdict: ACCEPTED
input |
---|
aztdvxzjwxtrludymvpradgbdpgnrq... |
correct output |
---|
aztdvxzjwxtrludymvpradgbdpgnrq... |
user output |
---|
aztdvxzjwxtrludymvpradgbdpgnrq... |
Test 6
Verdict: ACCEPTED
input |
---|
vvfigwwsyxbukedgcfyibvtbclybud... |
correct output |
---|
vvfigwwsyxbukedgcfyibvtbclybud... |
user output |
---|
vvfigwwsyxbukedgcfyibvtbclybud... |
Test 7
Verdict: ACCEPTED
input |
---|
abaabaaaaaaabaababbbbbbabaaabb... |
correct output |
---|
babbbabbbaabbbbaabbbbbbbbaabbb... |
user output |
---|
babbbabbbaabbbbaabbbbbbbbaabbb... |
Test 8
Verdict: ACCEPTED
input |
---|
txolestmgyepwrpofxyesjtsfkhjac... |
correct output |
---|
yxnbaabnxy |
user output |
---|
yxnbaabnxy |
Test 9
Verdict: ACCEPTED
input |
---|
ihpohpzoffel |
correct output |
---|
ff |
user output |
---|
ff |
Test 10
Verdict: ACCEPTED
input |
---|
flexflexvpqxierullgcfckjqflexf... |
correct output |
---|
cfc |
user output |
---|
cfc |
Test 11
Verdict: ACCEPTED
input |
---|
aabbabaabbaababbabaababbaabbab... |
correct output |
---|
abaababbaabbabaababbabaabbaaba... |
user output |
---|
abaababbaabbabaababbabaabbaaba... |
Test 12
Verdict: ACCEPTED
input |
---|
obsession |
correct output |
---|
ses |
user output |
---|
ses |
Test 13
Verdict: ACCEPTED
input |
---|
abcxcbaxcba |
correct output |
---|
abcxcba |
user output |
---|
abcxcba |
Test 14
Verdict: ACCEPTED
input |
---|
zzabc |
correct output |
---|
zz |
user output |
---|
zz |
Test 15
Verdict: ACCEPTED
input |
---|
aaccaabbaaccaaccaabbaaccaa |
correct output |
---|
aaccaabbaaccaaccaabbaaccaa |
user output |
---|
aaccaabbaaccaaccaabbaaccaa |
Test 16
Verdict: ACCEPTED
input |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
correct output |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
user output |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |