10590 2024. 04. 06 10:37:50 UVince Mágikus sorozat cpp17 Elfogadva 100/100 82ms 41216 KiB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

#define all(a) a.begin(),a.end()

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen("be2.txt","r",stdin);
    int n;
    cin >> n;
    
    vector<ll> z(n),a(n);
    stack<pair<ll,ll>> last;
    vector<vector<pair<ll,ll>>> mark(n);
    for (ll i = 0; i < n; i++)
    {
        
        cin>>z[i];
        if (z[i]!=0) {
            a[i]=1;
            while (!last.empty() && last.top().first+last.top().second-1<=i) last.pop();
            last.push({i,z[i]});
            if (i+z[i]<n) mark[i+z[i]].push_back({i,z[i]});
        }
        else {
            a[i]=2;
            auto [f,l]=last.top();
            if (f+l-1>=i){
                a[i]=a[i-f];
            }
            else {
                auto [p,q]=last.top();
                last.pop();
                if (!mark[i].empty()){
                    vector<bool> allowed(1e4,true);
                    for (auto [x,y] : mark[i]){
                        allowed[a[y]]=false;
                    }
                    for (int z=2;z<1e4;z++){
                        if (allowed[z]){
                            a[i]=z;
                            break;
                        }
                    }
                }
            }
        }
    }
    for (ll i : a) cout<<i<<" ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1696 KiB
2 Elfogadva 4ms 2712 KiB
subtask2 15/15
3 Elfogadva 3ms 2508 KiB
4 Elfogadva 3ms 2760 KiB
5 Elfogadva 3ms 2692 KiB
subtask3 15/15
6 Elfogadva 3ms 2600 KiB
7 Elfogadva 2ms 2540 KiB
8 Elfogadva 3ms 2760 KiB
9 Elfogadva 2ms 2812 KiB
10 Elfogadva 3ms 2936 KiB
subtask4 30/30
11 Elfogadva 3ms 3284 KiB
12 Elfogadva 3ms 3288 KiB
13 Elfogadva 3ms 3348 KiB
14 Elfogadva 3ms 3264 KiB
subtask5 40/40
15 Elfogadva 59ms 27080 KiB
16 Elfogadva 70ms 30064 KiB
17 Elfogadva 79ms 40152 KiB
18 Elfogadva 79ms 41216 KiB
19 Elfogadva 82ms 40572 KiB
20 Elfogadva 75ms 40348 KiB
21 Elfogadva 72ms 38116 KiB
22 Elfogadva 71ms 38684 KiB
23 Elfogadva 76ms 38212 KiB
24 Elfogadva 75ms 34156 KiB
25 Elfogadva 72ms 39876 KiB
26 Elfogadva 75ms 39824 KiB
27 Elfogadva 71ms 31412 KiB
28 Elfogadva 68ms 30716 KiB
29 Elfogadva 64ms 29220 KiB
30 Elfogadva 72ms 37508 KiB
31 Elfogadva 68ms 32812 KiB
32 Elfogadva 63ms 29748 KiB