제출 #239632

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
239632	2020-06-16 22:10:34	eohomegrownapps	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	503 ms	35816 KiB

palindromic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m = 1000000007;
ll p = 31;
ll pows[1000005];
void run(){
  string s;
  cin>>s;
  ll n= s.size();
  vector<ll> arr(n);
  for (ll i = 0; i<n; i++){
    arr[i]=s[i]-'a'+1;
  }
  vector<ll> ltor(n);//1,x+1,x^2+x+1...
  //vector<ll> rtol(n);//...x^2+x+1,x+1,1
  ltor[0]=arr[0];
  for (ll i = 1; i<n; i++){
    ltor[i]=(ltor[i-1]*p+arr[i])%m;
  }
  /*rtol[n-1]=arr[n-1];
  for (ll i = n-2; i>=0; i--){
    rtol[i]=(rtol[i+1]*p+arr[i])%m;
  }*/
  ll cnt = 0;
  ll prevstart = 0;
  for (ll i = 0; i<n; i++){
    //check if prevstart to i forms a block
    ll pref = ltor[i];
    ll sub = prevstart==0?0:(ltor[prevstart-1]*pows[i-prevstart+1])%m;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40