oj.uz

답안 #320602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320602 2020-11-09T08:29:43 Z AriaH Palindromic Partitions (CEOI17_palindromic) C++11
100 / 100
 794 ms 35184 KB 
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 1e6 + 10;
const int LOG = 24;

string s;

ll pw[2][N], Hsh[2][N], mod[2], base = 737, n;

pll baze(ll l, ll r)
{
    return Mp((Hsh[0][r] - ((Hsh[0][l - 1] * pw[0][r - l + 1]) % mod[0]) + mod[0]) % mod[0], (Hsh[1][r] - (Hsh[1][l - 1] * pw[1][r - l + 1] % mod[1]) + mod[1]) % mod[1]);
}

int is_eq(int l, int r, int sz)
{
    if(baze(l, l + sz - 1) == baze(r - sz + 1, r)) return 1;
    return 0;
}

void B()
{
    pw[0][0] = pw[1][0] = 1;
    for(int i = 1; i <= n; i ++)
    {
	for(int j = 0; j < 2; j ++)
	{
	    pw[j][i] = (pw[j][i - 1] * base) % mod[j];
	    Hsh[j][i] = (Hsh[j][i - 1] * base + s[i] - 'a' + 1) % mod[j];
	}
    }
}

inline void solve()
{
    cin >> s;
    n = (int)s.size();
    s = "." + s;
    B();
    int l = 1, r = n, ans = 1, sz = 1;
    while(l <= r)
    {
	while(l + sz < n + 1 && r - sz + 1 > 1 && !is_eq(l, r, sz)) sz ++;
	if(l + sz - 1 >= r - sz + 1) break;
	if(l + sz == r - sz + 1) { ans ++; break; }
	ans += 2;
	l += sz;
	r -= sz;
	sz = 1;
    }
    cout << ans << endl;
}

int main()
{
    mod[0] = 1e9 + 7;
    mod[1] = 1e9 + 9;
    int q;
    cin >> q;
    while(q--)
    {
	solve();
    }
    return 0;
}
/*!
        stay away from negative people they have a problem for every solution !
*/

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 8 ms 748 KB Output is correct
11 Correct 6 ms 748 KB Output is correct
12 Correct 10 ms 748 KB Output is correct
13 Correct 7 ms 620 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 8 ms 748 KB Output is correct
11 Correct 6 ms 748 KB Output is correct
12 Correct 10 ms 748 KB Output is correct
13 Correct 7 ms 620 KB Output is correct
14 Correct 770 ms 33656 KB Output is correct
15 Correct 431 ms 33760 KB Output is correct
16 Correct 794 ms 35184 KB Output is correct
17 Correct 404 ms 17812 KB Output is correct