Submission #10,163

2024-03-28 22:10:18

cpp17

Accepted 100/100

100ms

73496 KiB

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

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin>>N;
	vector<int>v(N);
	for(int i=0;i<N;i++){
		cin>>v[i];
	}
	v[0]=1;
	vector<int>w(N);
	vector<set<int>>u(N+1);
	deque<int>s;
	for(int i=0;i<N;i++){
		s.push_back(i);
		while(!s.empty()&&s.front()+v[s.front()]<=i){
			s.pop_front();
		}
		u[i+v[i]].insert(w[v[i]]);
		int x=1;
		while(u[i].count(x))x++;
		w[i]=s.empty()?x:w[i-s.front()];
		cout<<w[i]+1<<' ';
	}
	cout<<'\n';
	return 0;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	3ms	1824 KiB
		2	Accepted	6ms	4120 KiB
subtask2	15/15
		3	Accepted	4ms	2784 KiB
		4	Accepted	4ms	3136 KiB
		5	Accepted	4ms	3220 KiB
subtask3	15/15
		6	Accepted	3ms	2764 KiB
		7	Accepted	3ms	2988 KiB
		8	Accepted	3ms	3076 KiB
		9	Accepted	3ms	3284 KiB
		10	Accepted	3ms	3132 KiB
subtask4	30/30
		11	Accepted	4ms	3820 KiB
		12	Accepted	4ms	3804 KiB
		13	Accepted	4ms	3752 KiB
		14	Accepted	3ms	3960 KiB
subtask5	40/40
		15	Accepted	90ms	69216 KiB
		16	Accepted	89ms	64536 KiB
		17	Accepted	82ms	49980 KiB
		18	Accepted	82ms	54160 KiB
		19	Accepted	83ms	52144 KiB
		20	Accepted	78ms	48120 KiB
		21	Accepted	76ms	43668 KiB
		22	Accepted	75ms	42756 KiB
		23	Accepted	74ms	43300 KiB
		24	Accepted	82ms	58448 KiB
		25	Accepted	76ms	44028 KiB
		26	Accepted	75ms	43408 KiB
		27	Accepted	96ms	63684 KiB
		28	Accepted	93ms	72180 KiB
		29	Accepted	100ms	73496 KiB
		30	Accepted	79ms	46856 KiB
		31	Accepted	85ms	60748 KiB
		32	Accepted	90ms	69200 KiB