Cod sursa(job #471246)

Utilizator piekarskaAnna Piekarska piekarska Data 17 iulie 2010 21:45:25
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#define MAXN 300010
#define ULIM 5000000
using namespace std;
int N;
char S[ULIM+5];
int V[MAXN*2];
int active[MAXN],inactive[MAXN];


int main(){

	freopen("congr.in","r",stdin);
	freopen("congr.out","w",stdout);

	scanf("%d\n",&N);

	fgets(S+1,ULIM,stdin);

	int POZ=1;

	for (int i=1;i<(N*2);++i){
		while (S[POZ]<'0' || S[POZ]>'9') ++POZ;
		int cn=0;

		while (S[POZ]>='0' && S[POZ]<='9'){
			cn*=10;
			cn+=S[POZ]-'0';
			++POZ;
		}

		V[i]=cn%N;
	}


	fclose(stdin);

	int Nac=N;
	int Nin=N-1;


	int csum=0;

	for (int i=1;i<=N;++i){
		active[i]=i;
		csum+=V[i];
		csum%=N;
	}

	for (int i=1;i<N;++i)
		inactive[i]=N+i;

	srand(time(NULL));

	while (csum){
		int p1=rand()%Nac;
		p1++;
		int p2=rand()%Nin;
		p2++;

		csum-=V[active[p1]];
		if (csum<0) csum+=N;

		csum+=V[inactive[p2]];
		if (csum>=N) csum-=N;

		int aux=active[p1];
		active[p1]=inactive[p2];
		inactive[p2]=aux;
	}

	for (int i=1;i<Nac;++i)
		printf("%d ",active[i]);

	printf("%d\n",active[Nac]);


	fclose(stdout);

	return 0;
}