Cod sursa(job #465006)

Utilizator S7012MYPetru Trimbitas S7012MY Data 22 iunie 2010 20:56:26
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.88 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <bitset>
using namespace std;
#define DN 50002

long long poz[DN],npoz,neg[DN],nneg,n,S,smea,sir[DN];
bitset <DN> rez;

int main()
{
	srand(time(NULL));
	int i;
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	for(scanf("%lld %lld",&n,&S),i=1;i<=n; i++) scanf("%lld",&sir[i]);
	for(i=1; i<=n;i++) {
		if(smea>S) {
			smea-=sir[i];
			neg[++nneg]=i;
		}
		else {
			smea+=sir[i];
			rez[i]=1;
			poz[++npoz]=i;
		}
	}
	while(smea!=S ) {
		if(smea>S)  {
			i=rand()%npoz+1;
			smea-=2*sir[poz[i]];
			rez[poz[i]]=0;
			neg[++nneg]=poz[i];
			poz[i]=poz[npoz--];
		}
		else {
			i=rand()%nneg+1;
			smea+=2*sir[neg[i]];
			rez[neg[i]]=1;
			poz[++npoz]=neg[i];
			neg[i]=neg[nneg--];
		}
	}
	for(i=1; i<=n; i++)
		if(rez[i]) printf("+");
		else printf("-");
	return 0;
}