Cod sursa(job #757815)

Utilizator darrenRares Buhai darren Data 13 iunie 2012 16:19:27
Problema Congr Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <ctime>
#include <cstdlib>
#include <fstream>

using namespace std;

int N, A[600002];
int s1[300002], s2[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;
	
	srand(time(0));
	while (sum != 0)
	{
		int out = rand() % N + 1, in = rand() % (N - 1);
		sum -= A[s1[out]], sum += A[s2[in]];
		swap(s1[out], s2[in]);
		
		if (sum < 0) sum += N;
		if (sum >= N) sum -= N;
	}
	
	for (int i = 1; i <= N; ++i)
		fout << s1[i] << ' ';
	fout << '\n';
	
	fin.close();
	fout.close();
}