답안 #500288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500288	2021-12-30T15:41:05 Z	pooyashams	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	51 ms	15044 KB

palindromic

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 1e6+10;
const int base = 541;
const int mod = 1e9+7;

int kmp[maxn];
int bpw[maxn];
int n;
string str;

inline void solve()
{
	cin >> str;
	n = str.size();
	int o = 0;
	int s = 0;
	int e = n-1;
	int h1 = str[s++];
	int h2 = str[e--];
	int l = 1;
	int mid = n/2 - (1-n%2);
	for(int i = 0; i < mid; i++)
	{
		if(h1 == h2)
		{
			o += 2;
			h1 = str[s++];
			h2 = str[e--];
			l = 1;
		}
		else
		{
			h1 = (1ll*h1*base+str[s++]) % mod;
			h2 = (1ll*bpw[l++]*str[e--]+h2) % mod;
		}
	}
	if(h1 == h2 and n % 2 == 0)
		o += 2;
	else
		o += 1;
	cout << o << endl;
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	bpw[0] = 1;
	for(int i = 1; i < maxn; i++)
		bpw[i] = 1ll*bpw[i-1]*base%mod;
	int T; cin >> T;
	while(T--)
	{
		solve();
	}
	return 0;
}

Subtask #1

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4224 KB	Output is correct
2	Correct	7 ms	4228 KB	Output is correct
3	Correct	8 ms	4172 KB	Output is correct
4	Correct	8 ms	4212 KB	Output is correct
5	Correct	8 ms	4172 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4224 KB	Output is correct
2	Correct	7 ms	4228 KB	Output is correct
3	Correct	8 ms	4172 KB	Output is correct
4	Correct	8 ms	4212 KB	Output is correct
5	Correct	8 ms	4172 KB	Output is correct
6	Correct	7 ms	4172 KB	Output is correct
7	Correct	8 ms	4152 KB	Output is correct
8	Correct	7 ms	4176 KB	Output is correct
9	Correct	7 ms	4172 KB	Output is correct

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4224 KB	Output is correct
2	Correct	7 ms	4228 KB	Output is correct
3	Correct	8 ms	4172 KB	Output is correct
4	Correct	8 ms	4212 KB	Output is correct
5	Correct	8 ms	4172 KB	Output is correct
6	Correct	7 ms	4172 KB	Output is correct
7	Correct	8 ms	4152 KB	Output is correct
8	Correct	7 ms	4176 KB	Output is correct
9	Correct	7 ms	4172 KB	Output is correct
10	Correct	8 ms	4296 KB	Output is correct
11	Correct	9 ms	4300 KB	Output is correct
12	Correct	9 ms	4244 KB	Output is correct
13	Correct	10 ms	4248 KB	Output is correct

Subtask #4

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4224 KB	Output is correct
2	Correct	7 ms	4228 KB	Output is correct
3	Correct	8 ms	4172 KB	Output is correct
4	Correct	8 ms	4212 KB	Output is correct
5	Correct	8 ms	4172 KB	Output is correct
6	Correct	7 ms	4172 KB	Output is correct
7	Correct	8 ms	4152 KB	Output is correct
8	Correct	7 ms	4176 KB	Output is correct
9	Correct	7 ms	4172 KB	Output is correct
10	Correct	8 ms	4296 KB	Output is correct
11	Correct	9 ms	4300 KB	Output is correct
12	Correct	9 ms	4244 KB	Output is correct
13	Correct	10 ms	4248 KB	Output is correct
14	Correct	41 ms	15044 KB	Output is correct
15	Correct	31 ms	10388 KB	Output is correct
16	Correct	51 ms	14508 KB	Output is correct
17	Correct	22 ms	9976 KB	Output is correct