oj.uz

Submission #105494

# Submission time Handle Problem Language Result Execution time Memory
105494 2019-04-12T16:43:15 Z JakubLap Palinilap (COI16_palinilap) C++11
100 / 100
 129 ms 23908 KB 
// Autor: Ivan Katanic

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long llint;

const int MAX = 100100;
const int H = 9973;
const int mod = 1e9 + 7;

int pw[MAX];

int h[MAX];
int hr[MAX];
char s[MAX];
char sr[MAX];
int n;

void calcHashes(char* s, int* h) {
  h[0] = 1;
  for (int i = 0; i < n; ++i)
    h[i+1] = (h[i]*1LL*H + s[i]) % mod;
}

int getHash(int* h, int a, int b) {
  return ((h[b+1] - h[a]*1LL*pw[b-a+1]) % mod + mod) % mod;
}

bool revEqual(int a, int b, int c, int d) {
  return getHash(h, a, b) == getHash(hr, n-d-1, n-c-1);
}

int main(void) {
  scanf("%s", s);
  n = strlen(s);

  pw[0] = 1;
  for (int i = 0; i < n; ++i)
    pw[i+1] = (pw[i]*1LL*H) % mod;
  
  for (int i = 0; i < n; ++i)
    sr[i] = s[n-i-1];
  calcHashes(s, h);
  calcHashes(sr, hr);

  static llint f[MAX][26]; // created 
  static llint fk[MAX], fl[MAX]; // destroyed

  llint base = 0;
  for (int i = 0; i < n; ++i)
    for (int j = i; j <= i+1; ++j) {
      int lo = 0, hi = min(i+1, n-j);
      while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (revEqual(i-mid+1, i, j, j+mid-1)) lo = mid;
        else hi = mid - 1;
      }
      int r = lo;
      base += r;

      if (i == j) { // odd
        fk[j+1] += -1, fk[j+r] -= -1;
        fl[j+1] += j+r, fl[j+r] -= j+r;
        
        fk[i-r+1] += 1, fk[i] -= 1;
        fl[i-r+1] += -(i-r), fl[i] -= -(i-r);
      } else { // even
        fk[j] += -1, fk[j+r] -= -1;
        fl[j] += j+r, fl[j+r] -= j+r;
        
        fk[i-r+1] += 1, fk[i+1] -= 1;
        fl[i-r+1] += -(i-r), fl[i+1] -= -(i-r);
      }
      
      int x = i-r, y = j+r;
      if (x < 0 || y >= n) continue;
    
      r++;
      lo = 0, hi = min(i+1, n-j) - r;
      while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (revEqual(x-mid, x-1, y+1, y+mid)) lo = mid;
        else hi = mid - 1;
      }

      f[x][s[y]-'a'] += lo+1;
      f[y][s[x]-'a'] += lo+1;
    }
  
  llint best_change = 0;
  llint k = 0, l = 0;
  for (int i = 0; i < n; ++i) {
    k += fk[i], l += fl[i];
    for (int j = 0; j < 26; ++j)
      if (j+'a' != s[i]) {
        best_change = max(best_change, f[i][j] - (llint(i)*k + l));
      }
  }

  printf("%lld\n", base + best_change);
  return 0;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1536 KB Output is correct
2 Correct 5 ms 1588 KB Output is correct
3 Correct 7 ms 1536 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct
7 Correct 8 ms 1536 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 23544 KB Output is correct
2 Correct 73 ms 23636 KB Output is correct
3 Correct 114 ms 23744 KB Output is correct
4 Correct 114 ms 23764 KB Output is correct
5 Correct 102 ms 23736 KB Output is correct
6 Correct 100 ms 23672 KB Output is correct
7 Correct 114 ms 23720 KB Output is correct
8 Correct 49 ms 3448 KB Output is correct
9 Correct 111 ms 23644 KB Output is correct
10 Correct 98 ms 23772 KB Output is correct
11 Correct 78 ms 23772 KB Output is correct
12 Correct 107 ms 23852 KB Output is correct
13 Correct 129 ms 23744 KB Output is correct
14 Correct 124 ms 23672 KB Output is correct
15 Correct 100 ms 23840 KB Output is correct
16 Correct 112 ms 23732 KB Output is correct
17 Correct 121 ms 23908 KB Output is correct
18 Correct 114 ms 23672 KB Output is correct
19 Correct 107 ms 23672 KB Output is correct