Life on Mars?

Recently, the top-secret space vehicle Stardust was launched by the Association for the Cosmos Mission, ACM for short. The sole purpose of this mission is to collect scientific data regarding the existence of life on Mars. As a matter of fact, Stardust is an unmanned vehicle.

The Stardust Atmospheric and Surface Composition Spectrometer, Stardust's one-of-a-kind instrument, will measure the abundance of atmospheric gases around Mars and detect minerals in its surface materials. Once samples are taken, Stardust will transmit the findings to the Stardust Mission back to Earth. Nevertheless, scientists are afraid that upon the existence of Martians, Mars inhabitants, they will be clever enough to intercept messages, not only destroying them but also faking them.

An Stardust message is a non-empty sequence S = S(0)  S(1)  ...  S(n - 1) of natural numbers. The blank is used to delimit the elements of the sequence. A message is considered valid if there is a permutation of S , say S' , such that S' is idempotent, that is, for all 0 i < | S'| it holds that S'(S'(i)) = S'(i) . Any non-valid sequence is considered hacked.

You have been assigned to the Stardust Mission. Your task is to write an efficient verifier for the messages received from the Stardust.

Input 

The input consists of several test cases, one per line. Each test case contains a Stardust message: a non-empty sequence S = S(0)  S(1)  ...  S(n - 1) of natural numbers ( 1 n 10⁵ ). The blank is used to delimit the elements of the sequence.

The end of the input is indicated when the Stardust message is ``0''. Do not proccess this last line.

Output 

For each case in the input, print one line. If the input message is valid, any idempotent permutation of the input message S must be printed following the format of the input messages. If the input message is hacked, the warning ``Message hacked by the Martians!!!'' must be printed in a single line.

Sample Input 

2 0 1
2 1 1
3 2 2
2 2 2
1 2 2 1 1
2 4 1 3 0
2 4 2 3 0
2 4 6 3 0
5 8 1 9 4 0 7 11 2 6 10 3
5 2 1 2 4 0 7 11 2 6 2 3
1 2 1 2 1 0 7 11 2 6 2 1
1 2 1 2 1 0 7 7 2 6 2 1
1 2 1 2 1 0 7 7 2 6 12 1
0

Sample Output 

0 1 2
1 1 2
Message hacked by the Martians!!!
2 2 2
1 1 2 1 2
0 1 2 3 4
0 2 2 3 4
Message hacked by the Martians!!!
0 1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 4 5 6 7 2 2 2 11
0 1 2 1 1 1 6 7 2 2 2 11
0 1 2 1 1 1 6 7 2 2 2 7
Message hacked by the Martians!!!

---

Colombia'2008

觀察一下，就能發現將不重複的數字收集後，
就將其 number 放入 S'[number] = number，剩餘的隨便放即可。
但是如果 number 超過陣列索引值，即 number >= n 則無解。


#include <stdio.h>
#include <queue>
#include <iostream>
#include <sstream>
#include <string.h>
using namespace std;

int main() {
    string line;
    while(getline(cin, line)) {
        stringstream sin(line);
        int n = 0, S[10005];
        while(sin >> S[n])  n++;
        if(n == 1 && S[0] == 0)
            break;
        int St[10005], i;
        memset(St, -1, sizeof(St));
        queue<int> Q;
        int err = 0;
        for(i = 0; i < n && !err; i++) {
            if(S[i] >= n)   err = 1;
            else {
                if(St[S[i]] == -1)
                    St[S[i]] = S[i];
                else
                    Q.push(S[i]);
            }
        }
        if(err) {
            puts("Message hacked by the Martians!!!");
            continue;
        }
        for(i = 0; i < n; i++) {
            if(St[i] == -1) {
                St[i] = Q.front();
                Q.pop();
            }
        }
        for(i = 0; i < n; i++) {
            if(i)   putchar(' ');
            printf("%d", St[i]);
        }
        puts("");
    }
    return 0;
}