CSES - APIO 2014 - Results
Submission details
Task:Palindromes
Sender:ArktinenKarpalo
Submission time:2019-03-24 19:19:52 +0200
Language:C++
Status:READY
Result:23
Feedback
groupverdictscore
#1ACCEPTED8
#2ACCEPTED15
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3, 4, 5details
#2ACCEPTED0.02 s1, 2, 3, 4, 5details
#3ACCEPTED0.01 s1, 2, 3, 4, 5details
#4ACCEPTED0.02 s1, 2, 3, 4, 5details
#5ACCEPTED0.01 s1, 2, 3, 4, 5details
#6ACCEPTED0.02 s1, 2, 3, 4, 5details
#7ACCEPTED0.01 s1, 2, 3, 4, 5details
#8ACCEPTED0.02 s1, 2, 3, 4, 5details
#9ACCEPTED0.02 s1, 2, 3, 4, 5details
#10ACCEPTED0.02 s1, 2, 3, 4, 5details
#11ACCEPTED0.02 s1, 2, 3, 4, 5details
#12ACCEPTED0.02 s1, 2, 3, 4, 5details
#13ACCEPTED0.03 s1, 2, 3, 4, 5details
#14ACCEPTED0.01 s1, 2, 3, 4, 5details
#15ACCEPTED0.02 s1, 2, 3, 4, 5details
#16ACCEPTED0.02 s1, 2, 3, 4, 5details
#17ACCEPTED0.02 s1, 2, 3, 4, 5details
#18ACCEPTED0.02 s1, 2, 3, 4, 5details
#19ACCEPTED0.01 s1, 2, 3, 4, 5details
#20ACCEPTED0.01 s1, 2, 3, 4, 5details
#21ACCEPTED0.01 s1, 2, 3, 4, 5details
#22ACCEPTED0.02 s1, 2, 3, 4, 5details
#23ACCEPTED0.01 s1, 2, 3, 4, 5details
#24ACCEPTED0.02 s1, 2, 3, 4, 5details
#25ACCEPTED0.01 s1, 2, 3, 4, 5details
#26ACCEPTED0.03 s1, 2, 3, 4, 5details
#27ACCEPTED0.01 s1, 2, 3, 4, 5details
#28ACCEPTED0.01 s1, 2, 3, 4, 5details
#29ACCEPTED0.02 s1, 2, 3, 4, 5details
#30ACCEPTED0.02 s1, 2, 3, 4, 5details
#31ACCEPTED0.02 s1, 2, 3, 4, 5details
#32ACCEPTED0.01 s1, 2, 3, 4, 5details
#33ACCEPTED0.04 s2, 3, 4, 5details
#34ACCEPTED0.05 s2, 3, 4, 5details
#35ACCEPTED0.01 s2, 3, 4, 5details
#36ACCEPTED0.05 s2, 3, 4, 5details
#37ACCEPTED0.02 s2, 3, 4, 5details
#38ACCEPTED0.03 s2, 3, 4, 5details
#39ACCEPTED0.06 s2, 3, 4, 5details
#40ACCEPTED0.04 s2, 3, 4, 5details
#41ACCEPTED0.05 s2, 3, 4, 5details
#42ACCEPTED0.03 s2, 3, 4, 5details
#43ACCEPTED0.02 s2, 3, 4, 5details
#44ACCEPTED0.05 s2, 3, 4, 5details
#45--3, 4, 5details
#46--3, 4, 5details
#47ACCEPTED0.07 s3, 4, 5details
#48ACCEPTED0.74 s3, 4, 5details
#49--3, 4, 5details
#50--3, 4, 5details
#51--3, 4, 5details
#52ACCEPTED0.25 s3, 4, 5details
#53ACCEPTED0.25 s3, 4, 5details
#54--3, 4, 5details
#55--4, 5details
#56--4, 5details
#57--4, 5details
#58--4, 5details
#59--4, 5details
#60--4, 5details
#61--4, 5details
#62--4, 5details
#63--4, 5details
#64--4, 5details
#65--5details
#66--5details
#67--5details
#68--5details
#69--5details
#70--5details
#71--5details
#72--5details
#73--5details
#74--5details
#75--5details
#76--5details

Compiler report

input/code.cpp: In function 'long long int q(int)':
input/code.cpp:48:5: warning: unused variable 'cnt' [-Wunused-variable]
  ll cnt = 0;
     ^~~
input/code.cpp: In function 'int main()':
input/code.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<=s.size(); i++) {
               ~^~~~~~~~~~
input/code.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<=s.size(); i += 2) {
               ~^~~~~~~~~~
input/code.cpp:88:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1 <= s.size())
      ~~~~^~~~~~~~~~~

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<18)
#define M 1000000007
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

ll p[303030], h[303030][2], A, B, ans;
string s, sr;

inline ll hsh1(int a, int b) {
	return ((h[b][0]-(h[a-1][0]*p[b-a+1])%B)+B)%B;
}
inline ll hsh2(int a, int b) {
	a = s.size()-a+1;
	b = s.size()-b+1;
	swap(a, b);
	return ((h[b][1]-(h[a-1][1]*p[b-a+1])%B)+B)%B;
}
inline ll ph(int a, int len) {
	if(len%2 == 0) {
		ll h1 = hsh1(a, a+len/2-1);
		ll h2 = hsh2(a+len/2, a+len-1);
		if(h1 != h2)
			return -1;
		else
			return h1;
	} else {
		ll h1 = hsh1(a, a+(len+1)/2-1);
		ll h2 = hsh2(a+(len+1)/2-1, a+len-1);
		if(h1 != h2)
			return -1;
		else
			return h1;
	}
	return -2;
}
ll lm = 1e9;
ll q(int len) {
	if(len >= lm)
		return -6;
	ll ret = 0;
	ll cnt = 0;
	map<ll, ll> mp;
	ll ub = s.size()-len+1;
	ret = 0;
	for(int i=1; i<=ub; i++) {
		if(ans-ret*len >= len*(ub-i+1)) {
			return -5;
		}
		ll luku = ph(i, len);
		if(luku != -1)
			ret = max((mp[luku]++)+1, ret);
	}
	return ret*len;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	srand(time(NULL));
	A = rand();
	B = M;
	cin >> s;
	if(s.size() == 1) {
		cout << 1;
		exit(0);
	}
	sr = s;
	reverse(sr.begin(), sr.end());
	p[0] = 1;
	for(int i=1; i<=s.size(); i++) {
		p[i] = (p[i-1]*A)%B;
		h[i][0] = (h[i-1][0]*A+s[i-1])%B;
		h[i][1] = (h[i-1][1]*A+sr[i-1])%B;
	}
	for(int i=1; i<10; i++)
		ans = max(q(rand()%s.size()), ans);
	for(int i=1; i<=s.size(); i += 2) {
		ll l1 = q(i);
		ll l2 = -3;
		if(i+1 <= s.size())
			l2 = q(i+1);
		if(l1 == l2 && l1 == 0)
			lm = min(lm, (ll)i);
		ans = max(max(ans, l1), l2);			
	}
	cout << ans;
}

Test details

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
abacaba

correct output
7

user output
7

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
www

correct output
4

user output
4

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
abacababa

correct output
9

user output
9

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
r

correct output
1

user output
1

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
xd

correct output
1

user output
1

Test 6

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
dd

correct output
2

user output
2

Test 7

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
opo

correct output
3

user output
3

Test 8

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
opoo

correct output
3

user output
3

Test 9

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
abacabadabacaba

correct output
15

user output
15

Test 10

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
xxxxxyxxxxyxxxxx

correct output
24

user output
24

Test 11

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
xxxyxxxyzzzabcdxxdcba

correct output
10

user output
10

Test 12

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
qpppppppwowpppppq

correct output
24

user output
24

Test 13

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
mqmwmemrmtymmmmmmmmqwertyeeeee...

correct output
25

user output
25

Test 14

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
mqmwmmmmmemrmtymmmmmmmmqwertye...

correct output
28

user output
28

Test 15

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
abcdefghijklmnopqrstuvwxyzz

correct output
2

user output
2

Test 16

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
abcdefghijklmnopqrstuvwxyz

correct output
1

user output
1

Test 17

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
apiodpdpdpdpdpgoodchallenge

correct output
15

user output
15

Test 18

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
pdpdpdpxdpdpdxdpdpdx

correct output
18

user output
18

Test 19

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
jejejejejejejejejejejejejejeje...

correct output
1176

user output
1176

Test 20

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
wzwzwzwzwzwzwzwzwzwzwzwzwzwzwz...

correct output
1225

user output
1225

Test 21

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
qsqsqsqsqsqsqianananananananan...

correct output
136

user output
136

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
hsoqhdnglglqqhqhqhqhqhqhqmyiyi...

correct output
45

user output
45

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
oooooooooooooooooooooooooooooo...

correct output
2500

user output
2500

Test 24

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

correct output
380

user output
380

Test 25

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

correct output
2304

user output
2304

Test 26

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
gggggggggtoooooooooccwwwwwwwww...

correct output
110

user output
110

Test 27

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
vlvivlvwvlvivlvkvlvivlvwvlvivl...

correct output
93

user output
93

Test 28

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
nbnenbnjnbnenbnxnbnenbnjnbnenb...

correct output
729

user output
729

Test 29

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
ydycydylydycydyodoycydylydycyd...

correct output
132

user output
132

Test 30

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
dzydpxreexldgbslbouxllaizermiy...

correct output
7

user output
7

Test 31

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
bpmerpingvjipwmenzzalhrsmrkmxv...

correct output
8

user output
8

Test 32

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
abbabaabbaababbabaababbaabbaba...

correct output
64

user output
64

Test 33

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
yhyhyhyhyhyhyhyhyhyhyhyhyhyhyh...

correct output
124251

user output
124251

Test 34

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
nknknknknknknknknknknknknknknk...

correct output
38226

user output
38226

Test 35

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
oooooooooooooooooooooooooooooo...

correct output
249500

user output
249500

Test 36

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
ktktktktktktktktktktktktktktkt...

correct output
5778

user output
5778

Test 37

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
gggggggggggggggggggggggggggggg...

correct output
247506

user output
247506

Test 38

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
dddddddddddddddddddddddddddddd...

correct output
248004

user output
248004

Test 39

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
tdtytdtxtdtytdtptdtytdtxtdtytd...

correct output
973

user output
973

Test 40

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
xfxfxfxfxfxfxfxfxfxfxfxfxfxfxf...

correct output
123753

user output
123753

Test 41

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

correct output
2346

user output
2346

Test 42

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
phxbzjihyzgshwcidlnkwkltarrnbv...

correct output
53

user output
53

Test 43

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
nkevzhqlzcmqmbvtbojxbbtvgsxkbh...

correct output
52

user output
52

Test 44

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
abbabaabbaababbabaababbaabbaba...

correct output
976

user output
976

Test 45

Group: 3, 4, 5

Verdict:

input
lnlnlnlnlnlnlnlnlnlnlnlnlnlnln...

correct output
12497500

user output
(empty)

Test 46

Group: 3, 4, 5

Verdict:

input
qhqhqhqhqhqhqhqhqhqhqhqhqhqhqh...

correct output
6481800

user output
(empty)

Test 47

Group: 3, 4, 5

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
25000000

user output
25000000

Test 48

Group: 3, 4, 5

Verdict: ACCEPTED

input
ffffffffffffffffffffffffffffff...

correct output
17816841

user output
17816841

Test 49

Group: 3, 4, 5

Verdict:

input
xlxixlxpxlxixlxexlxixlxpxlxixl...

correct output
9945

user output
(empty)

Test 50

Group: 3, 4, 5

Verdict:

input
elelelelelelelelelelelelelelel...

correct output
504100

user output
(empty)

Test 51

Group: 3, 4, 5

Verdict:

input
afamafacafamafakafamafacafamaf...

correct output
1512930

user output
(empty)

Test 52

Group: 3, 4, 5

Verdict: ACCEPTED

input
hmdqbxxvfzcxpohuffioztrgqgxkhf...

correct output
413

user output
413

Test 53

Group: 3, 4, 5

Verdict: ACCEPTED

input
xznwghgyngrjehtffuiepaedcvdova...

correct output
428

user output
428

Test 54

Group: 3, 4, 5

Verdict:

input
abbabaabbaababbabaababbaabbaba...

correct output
7232

user output
(empty)

Test 55

Group: 4, 5

Verdict:

input
bhbhbhbhbhbhbhbhbhbhbhbhbhbhbh...

correct output
1249925001

user output
(empty)

Test 56

Group: 4, 5

Verdict:

input
ususususususususususususususus...

correct output
396337935

user output
(empty)

Test 57

Group: 4, 5

Verdict:

input
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

correct output
2500050000

user output
(empty)

Test 58

Group: 4, 5

Verdict:

input
llllllllllllllllllllllllllllll...

correct output
1016525689

user output
(empty)

Test 59

Group: 4, 5

Verdict:

input
kvkikvklkvkikvkgkvkikvklkvkikv...

correct output
99645

user output
(empty)

Test 60

Group: 4, 5

Verdict:

input
pqpzpqpupqpzpqpbpqpzpqpupqpzpq...

correct output
78569380

user output
(empty)

Test 61

Group: 4, 5

Verdict:

input
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

correct output
82810000

user output
(empty)

Test 62

Group: 4, 5

Verdict:

input
vmlqjhjiwwzijupbzztlkcxbcdavxy...

correct output
3989

user output
(empty)

Test 63

Group: 4, 5

Verdict:

input
bcqqtvvdvexrttkgcbhmlhoasnlcek...

correct output
125529616

user output
(empty)

Test 64

Group: 4, 5

Verdict:

input
abbabaabbaababbabaababbaabbaba...

correct output
66664

user output
(empty)

Test 65

Group: 5

Verdict:

input
bnbnbnbnbnbnbnbnbnbnbnbnbnbnbn...

correct output
11250075000

user output
(empty)

Test 66

Group: 5

Verdict:

input
jzjzjzjzjzjzjzjzjzjzjzjzjzjzjz...

correct output
894243195

user output
(empty)

Test 67

Group: 5

Verdict:

input
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

correct output
22499400004

user output
(empty)

Test 68

Group: 5

Verdict:

input
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

correct output
2958163321

user output
(empty)

Test 69

Group: 5

Verdict:

input
xqxtxqxwxqxtxqxlxqxtxqxwxqxtxq...

correct output
298935

user output
(empty)

Test 70

Group: 5

Verdict:

input
zwzwzwzwzwzwzwzwzwzwzwzwzwzwzw...

correct output
1210831209

user output
(empty)

Test 71

Group: 5

Verdict:

input
hyhnhyhehyhnhyhlhyhnhyhehyhnhy...

correct output
303195156

user output
(empty)

Test 72

Group: 5

Verdict:

input
hnrootvymrwweaxjusfltkgyqyeioo...

correct output
11804

user output
(empty)

Test 73

Group: 5

Verdict:

input
yoljcehfgzraqykusrdwgqxdudzvep...

correct output
11813

user output
(empty)

Test 74

Group: 5

Verdict:

input
abbabaabbaababbabaababbaabbaba...

correct output
262144

user output
(empty)

Test 75

Group: 5

Verdict:

input
acbabcacbabcacbabcacbabcacbabc...

correct output
3750025000

user output
(empty)

Test 76

Group: 5

Verdict:

input
uptvtysodzujkjcvrzkzydggrhjjli...

correct output
184796836

user output
(empty)