Cod sursa(job #466858)

Utilizator blasterzMircea Dima blasterz Data 27 iunie 2010 19:32:55
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>

#define dim 8192

using namespace std;

char ax[dim];
int pz;

void cit (int &x)
{
	x = 0;

	while (ax[pz] < '0' || ax[pz] > '9')
		if (++pz == dim)
			fread (ax, 1, dim, stdin),pz = 0;

	while (ax[pz] >= '0' && ax[pz] <= '9')
	{
		 x = x * 10 + ax[pz] - '0';
		 if (++pz == dim)
			 fread (ax, 1, dim, stdin),pz =0;
	}

}


struct nod
{
	int x, poz;
};

struct cmp
{
	bool operator () (const nod &a, const nod &b)const
	{
		if (a.x < b.x) return 1;
		return 0;
	}
};


int v[600001];
nod a[600001];
int n, m;

int left[300001], right[300001];
int nl, nr;


void solve ()
{
	sort (a + 1, a + m + 1, cmp () );
	int i, j;

	nl = nr = 0;
	for (i = 1; i <= n; ++i)
		left[++nl] = a[i].poz;

	for (i = n + 1; i <= m; ++i)
		right[++nr] = a[i].poz;

	int rest = 0;

	for (i = 1; i <= nl; ++i)
		rest = (rest + v[left[i]] ) % n;

	int ntimes ;
	
	int restNou;
	int p, q;
	int aux;

	for (ntimes = 0; ; ++ntimes)
	{
		if (rest == 0)
			break;
		p = rand () % nl + 1;
		q = rand () % nr + 1;

		restNou = rest;
		restNou = ((restNou - v[left[p]]) % n + n) % n; 

		restNou = (restNou + v[right[q]]) % n;

		if (restNou < rest)
		{
			aux = left[p];
			left[p] = right[q];
			right[q] = aux;	
		
			rest = restNou;
		}

	}

	sort (left + 1, left + nl + 1);
	for (i = 1;i <= nl; ++i)
		printf ("%d ", left[i]);
	printf ("\n");

//	fprintf (stderr, "(%d)\n",rest); 
}

int main ()
{
	srand (time (0));
	freopen ("congr.in", "r", stdin);
	freopen ("congr.out", "w", stdout);
	cit (n);
	m = 2 * n - 1;

	int i;
	for (i = 1; i <= m; ++i)
	{
		cit (a[i].x);
		v[i] = a[i].x;
		a[i].poz = i;
	}
	
	solve ();

	return 0;
}