Cod sursa(job #609242)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 20 august 2011 13:29:19
Problema Semne Scor 65
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.04 kb
#include<stdio.h>
#include<cstdlib>
#include<ctime>

#define maxN 50005

FILE*f=fopen("semne.in","r");
FILE*g=fopen("semne.out","w");

int n,S,s1,s2,V1[maxN],Poz1[maxN],v1,V2[maxN],Poz2[maxN],v2,X[maxN],x,i;

inline void swap ( int &a , int &b ){
	int aux;
	aux = a; a = b; b = aux;
}

int main () {
	
	fscanf(f,"%d %d",&n,&S);
	
	for ( i = 0 ; i < n ; ++i ){
		fscanf(f,"%d",&V1[i]); ++v1; Poz1[i] = i;
		X[i] = 1; s1 += V1[i];
	}
	
	srand(time(0));
	
	while ( s1 != s2 + S ){
		if ( s1 > s2 + S ){
			x = rand() % v1; s1 -= V1[x]; s2 += V1[x];
			X[Poz1[x]] = 0;
			V2[v2] = V1[x]; Poz2[v2] = Poz1[x];
			++v2;
			swap(V1[x],V1[v1-1]);
			swap(Poz1[x],Poz1[v1-1]);
			--v1;
		}
		else{
			x = rand() % v2; s1 += V2[x]; s2 -= V2[x];
			X[Poz2[x]] = 1;
			V1[v1] = V2[x]; Poz1[v1] = Poz2[x];
			++v1;
			swap(V2[x],V2[v2-1]);
			swap(Poz2[x],Poz2[v2-1]);
			--v2;
		}
	}
	
	for ( i = 0 ; i < n ; ++i ){
		if ( X[i] )
			fprintf(g,"+");
		else
			fprintf(g,"-");
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}