UVa : 11508 (Life on Mars?)


1. initialize integer array p with -1

2. take inputs one by one in variable num

3. if p [num] == -1
then its never been found before
p [num] = num;

4. else if p [num] == num
then its a duplicate
store this value in another place, for example stack
after u finished all the inputs, this duplicate value can be inserted
any location of p, wheres the value is still -1

5. after taking all the inputs:
put the stored values in p, where there is still -1

6. suppose there are total n values in a line
if any of them is greater than or equals to n
output : Message hacked by the Martians!!!

Solution :

// http://uva.onlinejudge.org/external/115/11508.html
// Runtime : 0.020s
// Tag : sorting, ad-hoc

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

char a [N];
int p [N / 10 + 5];

int main ()
{
	while ( gets (a) && strcmp (a, "0") != 0 ) {
		memset (p, -1, sizeof (p));
		char *pch = strtok (a, " ");
		stack <int> s;
		int cnt = 0;

		while ( pch != NULL ) {
			int num = atoi (pch);
			if ( p [num] == -1 ) p [num] = num;
			else s.push (num);
			pch = strtok (NULL, " ");
			cnt++;
		}

		int sz = s.size ();

		for ( int i = 0; i < cnt; i++ )
			if ( p [i] == -1 ) sz--;

		if ( sz < 0 ) printf ("Message hacked by the Martians!!!\n");
		else {
			bool space = false;
			for ( int i = 0; i < cnt; i++ ) {
				if ( space ) printf (" "); space = true;
				if ( p [i] == -1 ) { printf ("%d", s.top ()); s.pop (); }
				else printf ("%d", p [i]);
			}
			printf ("\n");
		}
	}

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s