ZeroJudge B938: Kevin's Game

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

宣告一個 Vector<int> 來存每一個人的「下一個人是誰」，並且在宣告一個 Vector<int> 預設為 0 代表每一個人是否被殺過了。當一個人被殺掉時，要更新他的下一個人為被殺的人的下一個人。

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
Tags

Related Posts

Comments