3939 2023. 03. 05 23:40:11 zsombor Mágikus sorozat cpp17 Elfogadva 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]] << " ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 28ms 81472 KiB
2 Elfogadva 32ms 82092 KiB
subtask2 15/15
3 Elfogadva 29ms 81892 KiB
4 Elfogadva 37ms 82100 KiB
5 Elfogadva 30ms 82400 KiB
subtask3 15/15
6 Elfogadva 28ms 82352 KiB
7 Elfogadva 28ms 82356 KiB
8 Elfogadva 28ms 82648 KiB
9 Elfogadva 28ms 82912 KiB
10 Elfogadva 35ms 83032 KiB
subtask4 30/30
11 Elfogadva 37ms 82908 KiB
12 Elfogadva 29ms 83164 KiB
13 Elfogadva 37ms 83372 KiB
14 Elfogadva 37ms 83584 KiB
subtask5 40/40
15 Elfogadva 128ms 88468 KiB
16 Elfogadva 128ms 86716 KiB
17 Elfogadva 129ms 87416 KiB
18 Elfogadva 127ms 87352 KiB
19 Elfogadva 136ms 87312 KiB
20 Elfogadva 149ms 88112 KiB
21 Elfogadva 153ms 88012 KiB
22 Elfogadva 150ms 87952 KiB
23 Elfogadva 145ms 88056 KiB
24 Elfogadva 131ms 87972 KiB
25 Elfogadva 133ms 87824 KiB
26 Elfogadva 135ms 88340 KiB
27 Elfogadva 109ms 86304 KiB
28 Elfogadva 123ms 86828 KiB
29 Elfogadva 128ms 88640 KiB
30 Elfogadva 165ms 84396 KiB
31 Elfogadva 146ms 86928 KiB
32 Elfogadva 128ms 86880 KiB