CSES - Aalto Competitive Programming 2024 - wk9 - Homework - Results
Submission details
Task:Z-array
Sender:snude
Submission time:2024-11-02 13:16:10 +0200
Language:C++ (C++11)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.09 sdetails
#7ACCEPTED0.09 sdetails
#8ACCEPTED0.10 sdetails
#9ACCEPTED0.09 sdetails
#10ACCEPTED0.09 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.09 sdetails
#13ACCEPTED0.09 sdetails

Compiler report

input/code.cpp: In function 'int main(int, char**)':
input/code.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%s", n);
      |         ~~~~~^~~~~~~~~

Code

#include <bits/stdc++.h>
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");
}
/**
* This algorithm is pretty much the same algorithm presented in the textbook.
* Not very easy to not copy it fully, if one tries to implement the algorithm
* as described in the textbook.
*
* If this violates the course rules then give me a fail.
*/
void create_z_array(char s[], vector<int> &z, int n)
{
int r = 0, l = 0;
// cout << n << " ";
for (int i = 1; i < n; i++) {
// z[i] = max(0, min(z[i - l], r - i + 1));
// deb("e: i: %d l: %d, r: %d, z[i]: %d\n", i, l, r, z[i]);
if (i + z[i - l] < r) {
z[i] = z[i - l];
// z[i] = max(0, min(z[i - l], r - i + 1));
} else {
// z[i] = z[i - l];
z[i] = max(0, min(z[i - l], r - i + 1));
// deb("z[i - l]: %d, r - i + 1: %d\n", z[i - l], r - i + 1);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
// deb("while\n");
l = i;
r = i + z[i];
z[i]++;
}
}
// cout << z[i] << " ";
// deb("j: i: %d l: %d, r: %d, z[i]: %d\n", i, l, r, z[i]);
}
// z[0] = n;
}
int main(int argc, char *argv[])
{
ios::sync_with_stdio(0);
cin.tie(0);
// Read the input parameters
// string n
char n[1000000];
// cin >> n;
scanf("%s", n);
vector<int> z(1000000);
int len = strlen(n);
create_z_array(n, z, len);
// for (unsigned int i = 0; i < n.size(); i++) {
// cout << z[i] << " ";
// }
// char s = n[0];
// int i = 0;
z[0] = len;
for (int i = 0; i < len; i++) {
cout << z[i] << " ";
}
// while (s != '\0') {
// cout << z[i] << " ";
// i++;
// s = n[i];
// }
cout << "\n";
return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
aaaaaaaaaa

correct output
10 9 8 7 6 5 4 3 2 1 

user output
10 9 8 7 6 5 4 3 2 1 

Test 2

Verdict: ACCEPTED

input
ababababab

correct output
10 0 8 0 6 0 4 0 2 0 

user output
10 0 8 0 6 0 4 0 2 0 

Test 3

Verdict: ACCEPTED

input
aabababaaa

correct output
10 1 0 1 0 1 0 2 2 1 

user output
10 1 0 1 0 1 0 2 2 1 

Test 4

Verdict: ACCEPTED

input
ahtqqkhrrn

correct output
10 0 0 0 0 0 0 0 0 0 

user output
10 0 0 0 0 0 0 0 0 0 

Test 5

Verdict: ACCEPTED

input
mqdozmqdoz

correct output
10 0 0 0 0 5 0 0 0 0 

user output
10 0 0 0 0 5 0 0 0 0 

Test 6

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
1000000 999999 999998 999997 9...

user output
1000000 999999 999998 999997 9...
Truncated

Test 7

Verdict: ACCEPTED

input
ababababababababababababababab...

correct output
1000000 0 999998 0 999996 0 99...

user output
1000000 0 999998 0 999996 0 99...
Truncated

Test 8

Verdict: ACCEPTED

input
baaaabbabaabbbbaaaabbbababaaba...

correct output
1000000 0 0 0 0 1 2 0 3 0 0 1 ...

user output
1000000 0 0 0 0 1 2 0 3 0 0 1 ...
Truncated

Test 9

Verdict: ACCEPTED

input
ltpbdybvcpychbsplyonjfmdtsnqwt...

correct output
1000000 0 0 0 0 0 0 0 0 0 0 0 ...

user output
1000000 0 0 0 0 0 0 0 0 0 0 0 ...
Truncated

Test 10

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
1000000 99998 99997 99996 9999...

user output
1000000 99998 99997 99996 9999...
Truncated

Test 11

Verdict: ACCEPTED

input
abaababaab

correct output
10 0 1 3 0 5 0 1 2 0 

user output
10 0 1 3 0 5 0 1 2 0 

Test 12

Verdict: ACCEPTED

input
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

correct output
1000000 499999 499998 499997 4...

user output
1000000 499999 499998 499997 4...
Truncated

Test 13

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
1000000 147418 147417 147416 1...

user output
1000000 147418 147417 147416 1...
Truncated