QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136365#5440. P-P-PalindromeUrgantTeamWA 173ms54764kbC++232.9kb2023-08-08 05:08:472023-08-08 05:08:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-08 05:08:49]
  • 评测
  • 测评结果:WA
  • 用时:173ms
  • 内存:54764kb
  • [2023-08-08 05:08:47]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;

const int MOD = (int) 1e9 + 7;
const int P = 73;
const int MAXLEN = 1000000;

int hashs[MAXLEN + 5], step[MAXLEN + 5];
int man_even[MAXLEN + 5], man_odd[MAXLEN + 5];
int open[MAXLEN + 5], period[MAXLEN + 5];

vector <int> spis[MAXLEN + 5];
map <int, int> max_occur;

int get_hash(int lef, int rig)
{
	return (hashs[rig] - (ll) hashs[lef - 1] * step[rig - lef + 1] % MOD + MOD) % MOD; 	
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);

 	int test;
 	cin >> test;

 	step[0] = 1;
 	for (int i = 1; i <= MAXLEN; i++) step[i] = (ll) step[i - 1] * P % MOD;

 	for (int rep = 1; rep <= test; rep++)
 	{
 	 	string s;
 	 	cin >> s;

 	 	int n = (int) s.length();

 	 	for (int i = 1; i <= n; i++)
 	 		hashs[i] = ((ll) hashs[i - 1] * P + s[i - 1] - 'a' + 1) % MOD;

 	 	for (int i = 1; i <= n; i++) open[i] = 0;

 	 	{
 	 	 	int lef = 0, rig = 0;
 	 	 	for (int i = 1; i < n; i++)
 	 	 	{
 	 	 	 	int len = 0;
 	 	 	 	if (rig > i) len = min(rig - i, man_even[lef + rig - i - 1]);
 	 	 	 	while (i - len - 1 >= 0 && i + len < n && s[i - len - 1] == s[i + len]) len++;
 	 	 	 	man_even[i] = len;
 	 	 	 	if (i + len > rig) rig = i + len, lef = i - len + 1;
 	 	 	}

 	 	 	for (int i = 1; i < n; i++)
 	 	 		if (man_even[i] != 0) open[i - man_even[i] + 1] = max(open[i - man_even[i] + 1], i + man_even[i]);
 	 	}

 	 	{
 	 	    int lef = 0, rig = 0;
 	 	 	for (int i = 1; i <= n; i++)
 	 	 	{
 	 	 	 	int len = 0;
 	 	 	 	if (rig > i) len = min(rig - i, man_odd[lef + rig - i]);
 	 	 	 	while (i - len - 2 >= 0 && i + len < n && s[i - len - 2] == s[i + len]) len++;
 	 	 	 	man_odd[i] = len;
 	 	 	 	if (i + len > rig) rig = i + len, lef = i - len;
 	 	 	}

 	 	 	for (int i = 1; i <= n; i++)
 	 	 		open[i - man_odd[i]] = max(open[i - man_odd[i]], i + man_odd[i]);
 	 	}

 	 	for (int i = 1; i <= n; i++)
 	 		open[i] = max(open[i], open[i - 1] - 1);

 	 	for (int i = 1; i <= n; i++) spis[i].clear(), period[i] = 0;
 	 	for (int i = 1; i <= n; i++)
 	 		spis[open[i] - i + 1].pb(i);

 	 	for (int del = 1; del <= n; del++)
 	 		for (int kr = del; kr <= n; kr += del)
 	 			for (int num : spis[kr])
 	 			{
 	 				if (period[num] != 0) continue;

 	 			  	if (get_hash(num, num + kr - 1 - del) == get_hash(num + del, num + kr - 1)) period[num] = del;
 	 			}
 	 	for (int i = 1; i <= n; i++)
 	 	{
 	 		int hs = get_hash(i, i + period[i] - 1);
 	 		int mx = max(max_occur[hs], (open[i] - i + 1) / period[i]);
 	 		max_occur[hs] = mx;
 	 	}
 	}         

 	ll ans = 0;
 	for (const auto &[str, kol] : max_occur) ans += (ll) kol * kol;
 	cout << ans << '\n';
 	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 39964kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 7ms
memory: 40560kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 1ms
memory: 39580kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 4ms
memory: 40996kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 31ms
memory: 45064kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 43ms
memory: 43444kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: -100
Wrong Answer
time: 173ms
memory: 54764kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133577

result:

wrong answer 1st numbers differ - expected: '133586', found: '133577'