CSES - Aalto Competitive Programming 2024 - wk9 - Mon - Results
Submission details
Task:Buzzwords
Sender:snude
Submission time:2024-11-04 17:14:28 +0200
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#320.00 sdetails
#33ACCEPTED0.00 sdetails
#340.00 sdetails
#35ACCEPTED0.00 sdetails
#360.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.00 sdetails
#390.00 sdetails
#40ACCEPTED0.00 sdetails
#410.00 sdetails
#420.00 sdetails
#430.00 sdetails
#440.00 sdetails

Code

#include <bits/stdc++.h>
#include <cstring>

using namespace std;
using ll = long long;

// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#define debug_print(fmt, args...) printf(fmt, ##args)
#else
#define deb(fmt, args...)
#define debug_print(fmt, args...)
#endif

void print_array(vector<int> in, const string title = "Vector")
{
	debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
	for (unsigned int i = 0; i < in.size(); i++) {
		debug_print("%d ", in[i]);
	}
	debug_print("\nDEBUG: ] END\n");
}

void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
	debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
	for (unsigned int i = 0; i < in.size(); i++) {
		for (unsigned int j = 0; j < in[i].size(); j++) {
			debug_print("%d ", in[i][j]);
		}
		debug_print("\nDEBUG: ");
	}
	debug_print("DEBUG: ] END\n");
}

void create_z_array(string &s, vector<int> &z)
{
	int n = s.size();
	int r = 0, l = 0;
	for (int i = 1; i < n; i++) {
		if (i + z[i - l] < r) {
			z[i] = z[i - l];
		} else {
			z[i] = max(0, min(z[i - l], r - i + 1));
			while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
				l = i;
				r = i + z[i];
				z[i]++;
			}
		}
	}
}

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	// Read the input parameters
	// string n << cin;
	// scanf("%s", n);
	string n;
	getline(cin, n);

	int q;
	cin >> q;

	int res = 0;
	// deb("%s\n", n.c_str());
	string trash;
	getline(cin, trash);
	deb("q: %d\n", q);
	for (int i = 0; i < q; i++) {
		string buzz;
		getline(cin, buzz);
		// if (buzz.size() == 0) continue;
		// buzz[strcspn(buzz.c_str(), "\n")] = 0;
		// buzz[buzz.size() - 1] = '\0';
		// deb("%s\n", buzz.c_str());
		int s = buzz.size();
		string word = buzz.append("#").append(n);
		// deb("%s\n", word.c_str());
		vector<int> z(300);
		create_z_array(word, z);
		// print_array(z);
		// deb("buzz: %s\n", buzz.c_str());
		for (unsigned int j = s; j < z.size(); j++) {
			if (z[j] > s - 1) {
				res++;
				// deb("j: %d, z[j]: %d\n", j, z[j]);
			}
			// res += z[j];
		}
	}
	cout << res << "\n";

	return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
g fhe
395
a
aa
aafh
...

correct output
10

user output
10

Test 2

Verdict: ACCEPTED

input
s adh
372
a
ad
ae
...

correct output
6

user output
6

Test 3

Verdict: ACCEPTED

input
adcdb
20
a
aa
ab
...

correct output
9

user output
9

Test 4

Verdict: ACCEPTED

input
aaaaa
5
a
aa
aaa
...

correct output
15

user output
15

Test 5

Verdict: ACCEPTED

input
o zws
759
a
ab
abw
...

correct output
8

user output
8

Test 6

Verdict: ACCEPTED

input
aaaaa
5
a
aa
aaa
...

correct output
15

user output
15

Test 7

Verdict: ACCEPTED

input
ifv b
649
a
aaw
ac
...

correct output
10

user output
10

Test 8

Verdict: ACCEPTED

input
dbbdc
129
a
aa
aaab
...

correct output
15

user output
15

Test 9

Verdict: ACCEPTED

input
aaaaa
5
a
aa
aaa
...

correct output
15

user output
15

Test 10

Verdict: ACCEPTED

input
eeeab
9
a
b
c
...

correct output
5

user output
5

Test 11

Verdict: ACCEPTED

input
ghfhe d fd
430
a
aa
aafa
...

correct output
22

user output
22

Test 12

Verdict: ACCEPTED

input
syadhzdgck
275
a
ad
adh
...

correct output
53

user output
53

Test 13

Verdict: ACCEPTED

input
adcdbbbbba
256
a
aa
aaa
...

correct output
49

user output
49

Test 14

Verdict: ACCEPTED

input
aaaaaaaaaa
10
a
aa
aaa
...

correct output
55

user output
55

Test 15

Verdict: ACCEPTED

input
o zwspspfd
468
a
adks
afhsrhvwxn
...

correct output
45

user output
45

Test 16

Verdict: ACCEPTED

input
aaaaaaaaaa
10
a
aa
aaa
...

correct output
55

user output
55

Test 17

Verdict: ACCEPTED

input
i vbbjczpc
703
a
aa
abou
...

correct output
29

user output
29

Test 18

Verdict: ACCEPTED

input
d bdcbdbcb
128
a
aa
aab
...

correct output
42

user output
42

Test 19

Verdict: ACCEPTED

input
aaaaaaaaaa
10
a
aa
aaa
...

correct output
55

user output
55

Test 20

Verdict: ACCEPTED

input
eeeabcbabh
171
a
aac
aahg
...

correct output
34

user output
34

Test 21

Verdict: ACCEPTED

input
ghfhehdf ddciaicdehheefdihadaf...

correct output
246

user output
246

Test 22

Verdict: ACCEPTED

input
s adhzdgckekirkyowkirnflwfanrx...

correct output
52

user output
52

Test 23

Verdict: ACCEPTED

input
adcdbbbbbaaccabbbccd cabccacdb...

correct output
178

user output
178

Test 24

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
2518

user output
2518

Test 25

Verdict: ACCEPTED

input
oezws spfdzfasgxlquafowjzpe pv...

correct output
284

user output
284

Test 26

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
1387

user output
1387

Test 27

Verdict: ACCEPTED

input
ifvbbjczpcnpknimqvlttkngpe szx...

correct output
258

user output
258

Test 28

Verdict: ACCEPTED

input
dbbdcbdb bcaabb bccddbbbacbcdc...

correct output
36

user output
36

Test 29

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
3076

user output
3076

Test 30

Verdict: ACCEPTED

input
e eabcbabhdbcbaddebchdiga ggfb...

correct output
23

user output
23

Test 31

Verdict: ACCEPTED

input
ghfhehdff dci icdehheefdih daf...

correct output
248

user output
248

Test 32

Verdict:

input
s a hzdgckekirkyo kirnflw anrx...

correct output
27

user output
(empty)

Error:
double free or corruption (out)

Test 33

Verdict: ACCEPTED

input
adcdbbb baac abbbcc c abccacd ...

correct output
433

user output
433

Test 34

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
3427

user output
(empty)

Error:
double free or corruption (!prev)

Test 35

Verdict: ACCEPTED

input
oezwsp pf z asgxlquafowjzpekpv...

correct output
359

user output
359

Test 36

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
2126

user output
(empty)

Error:
double free or corruption (!prev)

Test 37

Verdict: ACCEPTED

input
ifvbbjczpcnpk imqvlttkngpeqszx...

correct output
395

user output
395

Test 38

Verdict: ACCEPTED

input
dbbdcbd cbcaabbabccddbb acbcdc...

correct output
242

user output
242

Test 39

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
4287

user output
(empty)

Error:
free(): invalid next size (normal)

Test 40

Verdict: ACCEPTED

input
eeeabcbabhd cb ddebchdigaiggfb...

correct output
15

user output
15

Test 41

Verdict:

input
ghfhehdffdd i icdehheefd hadaf...

correct output
431

user output
(empty)

Error:
double free or corruption (out)

Test 42

Verdict:

input
syadhzdgckekirkyow irnflwfanrx...

correct output
8039

user output
(empty)

Error:
double free or corruption (out)

Test 43

Verdict:

input
adcdbbbbbaaccabb ccdccabcc cdb...

correct output
9409

user output
(empty)

Error:
double free or corruption (out)

Test 44

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
168696

user output
(empty)

Error:
free(): invalid next size (normal)