oj.uz

Submission #69699

# Submission time Handle Problem Language Result Execution time Memory
69699 2018-08-21T11:47:48 Z Googal Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 6 ms 1960 KB 
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

const ll NMAX = 1e4;
const ll MOD = 1e9;
const ll base = 26;

ll t, n;
ll mult[1 + NMAX];
ll phash[1 + NMAX];

char s[NMAX + 10];

ll solve_hash(ll le, ll ri) {
  return (phash[ri] - phash[le - 1] * mult[ri - le + 1] + MOD * MOD) % MOD;
}

void compute_mult() {
  mult[0] = 1;

  for(ll i = 1; i <= NMAX; i++)
    mult[i] = mult[i - 1] * base % MOD;
}

int main()
{
  ios_base::sync_with_stdio(false);
  compute_mult();

  cin >> t;

  for(ll test = 1; test <= t; test++) {
    cin >> (s + 1);
    n = strlen(s + 1);

    for(ll i = 1; i <= n; i++)
      phash[i] = (phash[i - 1] * base + s[i]) % MOD;

    ll le = 1;
    ll ri = n;
    ll res = 0;

    while(le <= ri) {
      ll len = 1;

      while(le + len - 1 < ri - len + 1 && solve_hash(le, le + len - 1) != solve_hash(ri - len + 1, ri))
        len++;

      if(le + len - 1 >= ri - len + 1) {
        res++;
        break;
      }

      res += 2;
      le += len;
      ri -= len;
    }

    cout << res << '\n';
  }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 4 ms 740 KB Output is correct
5 Correct 3 ms 916 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 4 ms 740 KB Output is correct
5 Correct 3 ms 916 KB Output is correct
6 Correct 2 ms 916 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 2 ms 916 KB Output is correct
9 Correct 3 ms 916 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 4 ms 740 KB Output is correct
5 Correct 3 ms 916 KB Output is correct
6 Correct 2 ms 916 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 2 ms 916 KB Output is correct
9 Correct 3 ms 916 KB Output is correct
10 Correct 5 ms 1064 KB Output is correct
11 Correct 4 ms 1164 KB Output is correct
12 Correct 6 ms 1236 KB Output is correct
13 Correct 4 ms 1348 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 4 ms 740 KB Output is correct
5 Correct 3 ms 916 KB Output is correct
6 Correct 2 ms 916 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 2 ms 916 KB Output is correct
9 Correct 3 ms 916 KB Output is correct
10 Correct 5 ms 1064 KB Output is correct
11 Correct 4 ms 1164 KB Output is correct
12 Correct 6 ms 1236 KB Output is correct
13 Correct 4 ms 1348 KB Output is correct
14 Runtime error 4 ms 1960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -