Cod sursa(job #322530)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 9 iunie 2009 00:40:51
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#define FIN "semne.in"
#define FOUT "semne.out"
#define MAXN 50010
#define PB push_back
#define pB pop_back
using namespace std;
vector<int> Poz,Neg;
long long S;
int N;
int v[MAXN];
int semn[MAXN];

int main(void){

		freopen(FIN,"rt",stdin);
		freopen(FOUT,"wt",stdout);

		scanf("%d%lld",&N,&S);

		for (int i=1;i<=N;++i) scanf("%d",&v[i]);

		long long sum=0;

		for (int i=1;i<=N;++i)
				if (sum<S){

						sum+=v[i];
						Poz.PB(i);
						semn[i]=1;
				} else {

						sum-=v[i];
						Neg.PB(i);
						semn[i]=0;
				}

		srand(time(NULL));

		while (sum!=S)

				if (sum<S){

						int change=rand()%(Neg.size());
						sum+=((long long)2*v[Neg[change]]);
						semn[Neg[change]]=1;
						Poz.PB(Neg[change]);
						Neg[change]=Neg[Neg.size()-1];
						Neg.pB();
				} else {
						
						int change=rand()%(Poz.size());
						sum-=((long long)2*v[Poz[change]]);
						semn[Poz[change]]=0;
						Neg.PB(Poz[change]);
						Poz[change]=Poz[Poz.size()-1];
						Poz.pB();
				}
		for (int i=1;i<=N;++i)
				if (semn[i]){printf("+");} else {printf("-");}

		printf("\n");

		fclose(stdin);
		fclose(stdout);
		return 0;
}