oj.uz

Submission #47808

# Submission time Handle Problem Language Result Execution time Memory
47808 2018-05-07T12:56:51 Z Extazy Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 160 ms 61964 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 1000007;
const unsigned long long B1 = 131, B2 = 137, MOD = (1e9) + 7;

struct rolling_hash {
  unsigned long long h1,h2;

  rolling_hash(): h1(0), h2(0) {}

  void append(char a) {
    h1*=B1;
    h1+=a-'a'+1;

    h2*=B2;
    h2+=a-'a'+1;
    h2%=MOD;
  }

  bool operator ==(const rolling_hash &a) const {
    return h1==a.h1 && h2==a.h2;
  }
};

int tests,current_case;
int n;
char a[N];
unsigned long long pw1[N],pw2[N];
rolling_hash ph[N];

rolling_hash get_hash(int l, int r) {
  rolling_hash hr=ph[r],hl=ph[l-1];

  hl.h1*=pw1[r-l+1];
  hl.h2*=pw2[r-l+1];
  hl.h2%=MOD;

  hr.h1-=hl.h1;
  hr.h2-=hl.h2;
  hr.h2+=MOD;
  hr.h2%=MOD;

  return hr;
}

int go(int l, int r) {
  if(l>r) return 0;

  for(int len=1;l+len-1<=n/2;len++) {
    if(get_hash(l,l+len-1)==get_hash(r-len+1,r)) return 2+go(l+len,r-len);
  }

  return 1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i;
  rolling_hash h;

  pw1[0]=pw2[0]=1;
  for(i=1;i<N;i++) {
    pw1[i]=pw1[i-1]*B1;
    pw2[i]=pw2[i-1]*B2%MOD;
  }

  scanf("%d", &tests);
  for(current_case=1;current_case<=tests;current_case++) {
    scanf("%s", a+1);
    n=strlen(a+1);

    h=rolling_hash();
    for(i=1;i<=n;i++) {
      h.append(a[i]);
      ph[i]=h;
    }

    printf("%d\n", go(1,n));
  }

  return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tests);
   ~~~~~^~~~~~~~~~~~~~
palindromic.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", a+1);
     ~~~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 27 ms 31848 KB Output is correct
3 Correct 27 ms 31848 KB Output is correct
4 Correct 27 ms 31848 KB Output is correct
5 Correct 27 ms 31848 KB Output is correct
6 Correct 27 ms 31848 KB Output is correct
7 Correct 31 ms 31848 KB Output is correct
8 Correct 28 ms 31848 KB Output is correct
9 Correct 27 ms 31848 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 27 ms 31848 KB Output is correct
3 Correct 27 ms 31848 KB Output is correct
4 Correct 27 ms 31848 KB Output is correct
5 Correct 27 ms 31848 KB Output is correct
6 Correct 27 ms 31848 KB Output is correct
7 Correct 31 ms 31848 KB Output is correct
8 Correct 28 ms 31848 KB Output is correct
9 Correct 27 ms 31848 KB Output is correct
10 Correct 29 ms 31880 KB Output is correct
11 Correct 28 ms 32152 KB Output is correct
12 Correct 29 ms 32152 KB Output is correct
13 Correct 28 ms 32180 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 27 ms 31848 KB Output is correct
3 Correct 27 ms 31848 KB Output is correct
4 Correct 27 ms 31848 KB Output is correct
5 Correct 27 ms 31848 KB Output is correct
6 Correct 27 ms 31848 KB Output is correct
7 Correct 31 ms 31848 KB Output is correct
8 Correct 28 ms 31848 KB Output is correct
9 Correct 27 ms 31848 KB Output is correct
10 Correct 29 ms 31880 KB Output is correct
11 Correct 28 ms 32152 KB Output is correct
12 Correct 29 ms 32152 KB Output is correct
13 Correct 28 ms 32180 KB Output is correct
14 Correct 160 ms 42888 KB Output is correct
15 Correct 99 ms 48092 KB Output is correct
16 Correct 153 ms 57488 KB Output is correct
17 Correct 99 ms 61964 KB Output is correct