Submission details
Task:Line Segment Intersection
Sender:aalto26jh_022
Submission time:2026-11-11 15:48:19 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.00 sdetails

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> z(n, 0);
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) {
            z[i] = min(z[i - l], r - i);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    string out;
    out.reserve(n * 7 + 1);
    for (int i = 0; i < n; i++) {
        out += to_string(z[i]);
        out += (i + 1 < n ? ' ' : '\n');
    }
    cout << out;
    return 0;
}

Test details

Test 1

Verdict:

input
100000
9 7 1 8 8 -5 0 2
10 1 -1 2 -4 1 -7 3
10 2 -8 6 1 2 2 -1
-10 1 9 -7 4 -3 -5 0
...

correct output
NO
NO
NO
NO
NO
...

user output
6 0 0 0 0 0

Feedback: Output is shorter than expected

Test 2

Verdict:

input
100000
81 745 -967 768 -451 -490 -454...

correct output
NO
NO
YES
NO
YES
...

user output
6 0 0 0 0 0

Feedback: Output is shorter than expected

Test 3

Verdict:

input
100000
492853 -452834 -657156 -282543...

correct output
YES
YES
NO
YES
YES
...

user output
6 0 0 0 0 0

Feedback: Output is shorter than expected

Test 4

Verdict:

input
100000
788522666 939776556 -831492125...

correct output
NO
NO
NO
NO
NO
...

user output
6 0 0 0 0 0

Feedback: Output is shorter than expected

Test 5

Verdict:

input
1
1 6 6 6 4 4 1000000000 1000000...

correct output
YES

user output
1

Feedback: Incorrect character on line 1 col 1: expected "YES", got "1"

Test 6

Verdict:

input
1
-1000000000 1000000000 9999999...

correct output
NO

user output
1

Feedback: Incorrect character on line 1 col 1: expected "NO", got "1"