Kevin is a handyman + a one-day team assistant.
It's essential to bring maximum entertainment to the team members.
So he brought an activity called "Blind Man Touches the Elephant."
At the beginning, N people stand in a line.
Numbered from 1 to N.
Each time Kevin would instruct the person numbered k to kill the people behind him.
But... there are too many people! 0u0
The team spread over more than a kilometer.
And Kevin has poor eyesight, he can't see that far.
So please tell Kevin who got killed.
If this person is already dead or if he is the last person.
Please output "0u0 ... ?"
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line of input consists of two integers, N and M (1 ≤ N, M ≤ 10^6), representing that N people are standing in a row numbered from 1 to N.
The next line contains M integers, k₁, k₂, ..., kₘ (1 ≤ k ≤ N), representing that Kevin wants to kill the person next to the kᵢ-th person. | Each time, output the number of the person who is killed.
If it's not valid, output "0u0 ... ?". |
| 5 4 1 1 5 4 | 2 3 0u0 …… ? 5 |
Thought Process
Declare a vector to store "who is the next person" for each person, and also declare another vector initialized with 0 to indicate whether each person has been killed. When a person is killed, update the next person of the killed person to be the next person of the person who is killed.
Sample Code－ZeroJudge B938: Kevin's Game
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<int>live;
live.push_back(-1);
vector<pair<int, int>>v;
pair<int, int> a;
a.first = -1;
a.second = -1;
v.push_back(a);
for (int i = 1; i<=N; i++) {
pair<int, int>tmp;
tmp.first = i-1;
tmp.second = i+1;
if (i == 1) tmp.first = -1;
if (i == N) tmp.second = -1;
v.push_back(tmp);
live.push_back(0);
}
for (int i = 0; i<M; i++) {
int tmp;
cin >> tmp;
if (live[tmp] == -1) {
cout << "0u0 ...... ?\n";
continue;
}
const int next = v[tmp].second;
if (next == -1) {
cout << "0u0 ...... ?\n";
continue;
}
cout << next << "\n";
live[next] = -1;
v[tmp].second = v[next].second;
}
}
//ZeroJudge B938
//Dr. SeanXD