Cod sursa(job #517503)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 28 decembrie 2010 23:46:43
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

#define nmax 50101

#define file_in "semne.in"
#define file_out "semne.out"

long long A,S;
int N,V[nmax];
char semn[nmax];
vector<int> plus;
vector<int> minus;
int X,XX;

int main(){
	
	srand(time(NULL));
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %%ld", &N, &S);
	for (int i=1;i<=N;++i){
		 scanf("%d", &V[i]);
		 if (A+V[i]>S){
			 minus.push_back(i);
			 A-=V[i];
			 semn[i]=0;
		 }
		 else{
			 plus.push_back(i);
			 A+=V[i];
			 semn[i]=1;
		 }
	}
		 
	while(A!=S){

		if (A>S){
			X=rand()%plus.size();
			XX=plus[X];
		    A-=(V[XX]<<1);
            plus[X]=plus[plus.size()-1];
			plus.pop_back();
			minus.push_back(XX);
			semn[XX]=0;
		}
		else{
			X=rand()%minus.size();
			XX=minus[X];
		    A+=(V[XX]<<1);
            minus[X]=minus[minus.size()-1];
			minus.pop_back();
			plus.push_back(XX);
			semn[XX]=1;
		}
		
	}
	
	for (int i=1;i<=N;++i)
		 if (semn[i])
			 printf("+");
		 else
			 printf("-");
		 
	return 0;

}