Cod sursa(job #757818)

Utilizator darrenRares Buhai darren Data 13 iunie 2012 16:24:53
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <ctime>
#include <cstdlib>
#include <fstream>

using namespace std;

int N, A[600002];
int s1[300002], s2[300002];
int freq[300002];

int main()
{
	ifstream fin("congr.in");
	ofstream fout("congr.out");
	
	fin >> N;
	for (int i = 1; i <= 2 * N - 1; ++i)
	{
		fin >> A[i];
		A[i] %= N;
	}
	
	
	int sum = 0;
	for (int i = 1; i <= N; ++i)
	{
		sum += A[i];
		if (sum >= N) sum -= N;
		s1[++s1[0]] = i;
	}
	for (int i = N + 1; i <= 2 * N - 1; ++i)
	{
		s2[++s2[0]] = i;
		++freq[A[i]];
	}
	
	srand(time(0));
	while (sum != 0)
	{
		int out = rand() % N + 1, in = rand() % (N - 1);
		sum -= A[s1[out]];
		if (sum < 0) sum += N;
		
		if (freq[N - sum])
		{
			for (int i = 1; i <= s2[0]; ++i)
				if (A[s2[i]] == N - sum)
				{
					sum = 0;
					swap(s1[out], s2[i]);
					break;
				}
		}
		else
		{
			sum += A[s2[in]];
			++freq[A[s1[out]]], --freq[A[s2[in]]];
			swap(s1[out], s2[in]);
		}
		
		if (sum >= N) sum -= N;
	}
	
	for (int i = 1; i <= N; ++i)
		fout << s1[i] << ' ';
	fout << '\n';
	
	fin.close();
	fout.close();
}