Cod sursa(job #2230921)
| Utilizator |  Marius B mgnt |
Data | 12 august 2018 14:12:46 |
|---|---|---|---|
| Problema | PScPld | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 42.28 kb |
#define FOLD__SCOPE
#ifdef FOLD__SCOPE /// includes
#include <cstddef>
#include <fstream>
#include <limits>
#include <memory>
#endif
#ifdef FOLD__SCOPE /// typedefs
typedef ::std::size_t stsz;
typedef char stch;
typedef char unsigned stcu;
typedef long long unsigned stuw;
#endif
#ifdef FOLD__SCOPE /// typedefs
typedef ::std::ifstream stis;
typedef ::std::ofstream stos;
#endif
#ifdef FOLD__SCOPE /// typedefs
typedef ::std::string stsg;
#endif
#ifdef FOLD__SCOPE /// constants
stsz const min_n = 1;
stsz const max_n = 1000000;
#endif
#ifdef FOLD__SCOPE /// typedef
/// arch ― array of characters
/// armo ― array for Manacher's Algorithm to find palindromes of Odd length
/// arme ― array for Manacher's Algorithm to find palindromes of Even length
typedef stsz arch [ max_n ] ;
typedef stsz armo [ max_n ] ;
typedef stsz arme [ max_n ] ;
/// The canonical form for a string should be array of size_t elements,
/// considering that any array may be of size up to max size_t value.
/// arrc ― array of raw characters
typedef stch arrc [ max_n ] ;
#endif
#ifdef FOLD__SCOPE /// algorithm
void
manacher_odd
(
size_t const n
, arch const & S
, armo & L
)
noexcept
{
if (true) { /// Document.
/// Given a valid input, a string S of length n, S[0…n−1],
/// compute L[0…n−1], L[i] is the maximum value such that
/// S[i−L[i]+1…i−L[i]+1] is a palindrome of odd length
/// 2·L[i]−1, centered at i. We use Manacher's Algorithm!
}
if (true) { /// Validate.
/// Validate input.
if (max_n < n)
{
/// Invalid input.
return;
}
if (0 >= n)
{
/// Invalid input.
return;
}
}
if (true) { /// Solve.
/// Solve challenge.
L[0] = 1;
/// When at step i, i > 0, in variable R will be the value
/// max i ← 0 … i − 1 ∷ i + L[i]. In variable C will be
/// the smallest value a, 0 ≤ a < i so that a + L[a] = R.
stsz C = 0;
stsz R = 1;
stsz i = 1;
stsz q = 0;
stsz u = 0;
stsz v = 0;
stsz x = 0;
stsz z = 0;
for ( i = 1; n > i; ++ i )
{
if (true) { /// Pick.
/// Pick the most useful value x ≤ L[i].
/// Two cases:
if (R <= i)
{
/// CASE 1. i ∉ [C, C + L[C] − 1].
x = 1;
}
else
{
/// CASE 2. i ∈ [C, C + L[C] − 1].
/// C < i
/// i < R ⇔ i < C + L[C] ⇔ i ≤ C + L[C] − 1
/// i = C + (i − C) ≤ C + L[C] − 1
/// C − L[C] + 1 ≤ C − (i − C)
/// q ← C + (i − C).
/// Use the overlap of strings
/// S[q − L[q] + 1…q + L[q] − 1], and
/// S[C − L[C] + 1…C + L[C] − 1], to
/// to pick the maximum value for x such that
/// the string of length 2·x − 1, centered at i is
/// guaranteed to be a palindrome.
///
/// Also, keep this i, 2·x − 1 string a substring of
/// the C, 2·(R − C) - 1 string.
q = C - (i - C);
u = L[q];
v = R - i;
x = u < v ? u : v;
}
}
if (true) { /// Scan.
/// Scan until x becomes L[i].
while ( (x <= i) && (x < (n - i) ) && (S[i - x] == S[i + x]) )
{
++ x;
}
/// Scanning performs 0 steps when both i and q are contained in C.
/// When i goes out of C, i continues scanning with R+1, R+2, … .
/// This is why the Manacher's Algorithm is Linear in size of S.
}
if (true) { /// Update.
/// Update L[i], and, eventually, C, and R.
L[i] = x;
z = i + x;
if (z > R)
{
R = z;
C = i;
}
}
}
}
}
#endif
#ifdef FOLD__SCOPE /// algorithm
void
manacher_even
(
stsz const n
, arch const & S
, arme & L
)
noexcept
{
if (true) { /// Document.
/// Given input S[0…n−1], n ≤ max_n, compute array L[0…n−2].
/// L[i] is the length of longest palindrome of S centered at i and 1+i.
/// That is, L[i] is the largest integer greater than or equal to zero,
/// such that S[i−t] = S[(1+i)+t], t←0…L[i]−1.
}
if (true) { /// Validate.
if (max_n < n)
{
/// Invalid input.
return;
}
}
if (true) { /// Solve.
if (1 >= n)
{
/// Done.
return;
}
L[0] = (S[0] == S[1]) ? 1 : 0;
stsz C = 0;
stsz R = (1 + C) + L[C];
stsz i = 0;
stsz q = 0;
stsz u = 0;
stsz v = 0;
stsz x = 0;
stsz z = 0;
for ( i = 1; n - 1 > i; ++ i )
{
if (true) { /// Pick.
/// x ← L[C] ∷ t ← 0…x−1 ∷ S[C−t] == S[(1+C)+t],
/// R == (1 + C) + L[C].
///
/// q ← C − (i − (1+C))
///
/// Let's fold the string S in a ⊏ shape, with 1+C and C
/// indices positioned on the ⊏'s two corners, like so:
///
///
/// S[ C ], S[ C − 1], …, S[q], S[q−1], …,S[ C − L[C] + 1]
/// S[1+C], S[(1+C) + 1], …, S[i], S[1+i], …,S[(1+C) + L[C] − 1]
///
/// This layout should help us deriving the value of x.
if ( (R-1) <= i )
{
x = 0;
}
else
{
q = C - (i - (1 + C));
u = L[q - 1];
v = (R-1) - (1+i) + 1;
x = (u < v) ? u : v;
}
}
if (true) { /// Scan.
while ( (x <= i) && (x < (n - (1+i)) ) && (S[i-x] == S[(1+i)+x] ) )
{
x = 1 + x;
}
}
if (true) { /// Update.
L[i] = x;
z = (1 + i) + x;
if (R < z)
{
R = z;
C = i;
}
}
}
}
}
#endif
#ifdef FOLD__SCOPE /// dogma
/// canon, dogmă, etc.
bool
translate_into_canonical_form
(
stsz const n
, arrc const & S
, arch & C
)
{
if ( max_n < n )
{
/// Incorrect program.
return false;
}
/// cz ― char zero.
/// sm ― size_t max.
char const cz = '\0';
stsz const sm = ::std::numeric_limits < stsz > :: max ( ) ;
bool ok = false;
stsz i = 0;
stch h = 0;
stcu u = 0;
stsz v = 0;
for ( i = 0; n > i; ++ i )
{
h = S[i];
ok = (cz <= h);
if ( ! ok )
{
/// Implementation limit.
return false;
}
u = static_cast < stcu > (h);
ok = (sm >= u);
if ( ! ok )
{
/// Implementation limit.
return false;
}
v = static_cast < stsz > (u);
C[i] = v;
}
return true;
}
#endif
#ifdef FOLD__SCOPE /// pscpld
/// pprt ― pscpld struct
/// pscpld ― problemă simplă cu palindroame?
struct pprt
{
stsz n;
arrc B;
arch S;
armo O;
arme E;
stuw k;
pprt () noexcept;
}
;
pprt::pprt
()
noexcept
{
n = 0;
k = 0;
}
#endif
#ifdef FOLD__SCOPE /// typedef
/// RAII
typedef ::std::unique_ptr < pprt > ppup;
#endif
#ifdef FOLD__SCOPE /// demo
bool
demo
()
{
#ifdef FOLD__SCOPE /// memory
/// Memory management.
ppup uctx;
pprt * pctx = new pprt;
uctx.reset(pctx);
pprt & rctx = * pctx;
#endif
if (true) { /// read
/// Read input.
/// Validate input.
bool ok = false;
stis is ("pscpld.in");
stsg il;
getline(is, il);
stsz const n = il.size();
ok = ( (min_n <= n) &&
(max_n >= n) );
if ( ! ok )
{
/// Invalid input.
return false;
}
char const * p = il.c_str();
stsz i = 0;
char v = 0;
for ( i = 0; n > i; ++ i )
{
v = p[i];
ok = ( ( 'a' <= v ) && ( 'z' >= v ) );
if ( ! ok )
{
/// Invalid input.
return false;
}
}
/// Input is valid.
arrc & B = rctx.B;
for ( i = 0; n > i; ++ i )
{
B[i] = p[i];
}
arch & S = rctx.S;
ok = translate_into_canonical_form(n, B, S);
if ( ! ok )
{
/// Implementation limit.
return false;
}
rctx.n = n;
}
if (true) { /// solve
/// Solve problem instance.
stsz const n = rctx.n;
arch const & S = rctx.S;
armo & O = rctx.O;
arme & E = rctx.E;
stuw k = 0;
stsz i = 0;
stsz x = 0;
stuw v = 0;
manacher_odd (n, S, O);
manacher_even (n, S, E);
for ( i = 0; n > i; ++ i )
{
x = O[i];
v = x;
k = k + v;
}
for (i = 0; n - 1 > i; ++ i )
{
x = E[i];
v = x;
k = k + v;
}
rctx.k = k;
}
if (true) { /// write
/// Write answer.
stuw const k = rctx.k;
stos os ("pscpld.out");
os << k << '\n';
}
return true;
}
#endif
#ifdef FOLD__SCOPE /// main
int
main
()
{
int status = 0;
try
{
bool const ok = demo();
status = ( ok ? 0 : 1 );
}
catch ( ... )
{
status = 2;
}
return status;
}
#endif
