3939 2023. 03. 05 23:40:11 zsombor Mágikus sorozat cpp17 Accepted 100/100 165ms 88640 KiB 
#include <iostream>
#include <vector>
using namespace std;

int n, done = 1, a, b, cnt = 0;
vector <int> z(3e5, 0);
vector <int> p(3e5, 0);
vector <vector <int>> dif(3e5);
vector <int> root;
vector <vector <bool>> v(800, vector<bool>(3e5, true));
vector <int> val(3e5, 0);

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> z[i];
        p[i] = i;
    }
    for (int i = 1; i < n; i++) {
        for (int j = max(i, done); j < i + z[i]; j++) {
            p[j] = j - i;
        }
        done = max(done, i + z[i]);
        p[i] = p[p[i]];
    }
    for (int i = 1; i < n; i++) {
        a = z[i]; b = i + z[i];
        if (b < n) dif[a].push_back(b);
    }
    for (int i = 0; i < n; i++) {
        if (p[i] != i) { p[i] = p[p[i]]; continue; }
        a = cnt;
        for (int j = cnt - 1; j >= 0; j--) if (v[j][i]) a = j;
        if (a == cnt) { root.push_back(i); cnt++; val[i] = cnt; }
        p[i] = root[a];
        for (int j : dif[i]) v[a][j] = false;
    }
    for (int i = 0; i < n; i++) cout << val[p[i]] << " ";
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 28ms 81472 KiB
2 Accepted 32ms 82092 KiB
subtask2 15/15
3 Accepted 29ms 81892 KiB
4 Accepted 37ms 82100 KiB
5 Accepted 30ms 82400 KiB
subtask3 15/15
6 Accepted 28ms 82352 KiB
7 Accepted 28ms 82356 KiB
8 Accepted 28ms 82648 KiB
9 Accepted 28ms 82912 KiB
10 Accepted 35ms 83032 KiB
subtask4 30/30
11 Accepted 37ms 82908 KiB
12 Accepted 29ms 83164 KiB
13 Accepted 37ms 83372 KiB
14 Accepted 37ms 83584 KiB
subtask5 40/40
15 Accepted 128ms 88468 KiB
16 Accepted 128ms 86716 KiB
17 Accepted 129ms 87416 KiB
18 Accepted 127ms 87352 KiB
19 Accepted 136ms 87312 KiB
20 Accepted 149ms 88112 KiB
21 Accepted 153ms 88012 KiB
22 Accepted 150ms 87952 KiB
23 Accepted 145ms 88056 KiB
24 Accepted 131ms 87972 KiB
25 Accepted 133ms 87824 KiB
26 Accepted 135ms 88340 KiB
27 Accepted 109ms 86304 KiB
28 Accepted 123ms 86828 KiB
29 Accepted 128ms 88640 KiB
30 Accepted 165ms 84396 KiB
31 Accepted 146ms 86928 KiB
32 Accepted 128ms 86880 KiB