CSES - Aalto Competitive Programming 2024 - wk9 - Wed - Results
Submission details
Task:Longest palindrome
Sender:aalto2024j_005
Submission time:2024-11-06 16:21:19 +0200
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.46 sdetails
#4ACCEPTED0.60 sdetails
#5ACCEPTED0.71 sdetails
#6ACCEPTED0.71 sdetails
#7ACCEPTED0.71 sdetails
#8ACCEPTED0.71 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.17 sdetails
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.23 sdetails

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...