Cod sursa(job #678916)

Utilizator ProtomanAndrei Purice Protoman Data 12 februarie 2012 15:48:48
Problema Range minimum query Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

#define MAX 100010
#define pb push_back

using namespace std;

vector <int> mex[MAX];
int sg[MAX];

int main()
{
	//freopen("p7.in", "r", stdin);
	//freopen("p7.out", "w", stdout);

	for (int i = 1; i <= 100000; i++)
	{
		sort(mex[i].begin(), mex[i].end());
		
		for (int j = 0; j < mex[i].size(); )
			if (mex[i][j] == sg[i])
			{
				for (; j < mex[i].size() && mex[i][j] == sg[i]; j++);
				sg[i]++;
			}
			else break;

		int nr = i;
		int val = sg[i];
		for (int j = i - 1; j && nr + j <= 100000; j--)
		{
			val += sg[j];
			nr += j;
			mex[nr].pb(val);
		}
	}

	int testCases;
	for (scanf("%d", &testCases); testCases; testCases--)
	{
		int n, sXor = 0;
		scanf("%d", &n);

		for (int i = 1; i <= n; i++)
		{
			int c;
			scanf("%d", &c);
			sXor ^= sg[c];
		}

		if (sXor)
			printf("HARRY\n");
		else printf("RON\n");
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}