oj.uz

답안 #525066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525066 2022-02-10T15:33:29 Z Yazan_Alattar Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 0 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 200007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

struct Hash {
  ll SEED = 131,MOD = 1e9 + 7;
  vector<ll> ha;
  vector<ll> power;

  void build(string x) {
	power.resize(x.size());
	ha.resize(x.size());
    power[0] = 1;
    for(int i=1; i<(int)power.size(); i++) power[i] = (power[i-1] * SEED)%MOD;
    ha[0] = x[0];
    for(int i=1; i<(int)ha.size(); i++) ha[i] = (ha[i-1] * SEED + x[i])%MOD;
  }
  
  ll get(int i, int j) {
    ll ret = ha[j];
    if (i) ret -= (ha[i-1] * power[j - i + 1])%MOD;
    ret = (ret % MOD + MOD) % MOD;
    return ret;
  }
};

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--){
		string s;
		cin >> s;
		Hash Hs; Hs.build(s);
		int n = s.size(), st = 0, ans = 0;
		for(int i = 0; i < n / 2; ++i){
			if(Hs.get(st, i) == Hs.get(n - i - 1, n - st - 1)){
				ans += 2;
				st = i + 1;
			}
		}
		cout << ans + 1 << endl;
	}
	return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -