Cod sursa(job #890556)

Utilizator crushackPopescu Silviu crushack Data 25 februarie 2013 10:26:02
Problema Semne Scor 20
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#define NMax 50010
using namespace std;

typedef long long ll;
const char IN[]="semne.in",OUT[]="semne.out";

int N,solved; ll S;
int v[NMax],sol[NMax],idx[NMax];

bool cmp(int x,int y){
	return v[x]>v[y];
}

void randomize(){
	for (int i=1;i<=N;++i) sol[i]=rand()%2;
}

int main()
{
	int i,j;ll sum,s;
	srand(time(NULL));
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&S);
	for (i=1;i<=N;++i) scanf("%d",v+i);
	fclose(stdin);

	for (i=1;i<=N;++i) idx[i]=i;
	sort(idx+1,idx+N+1,cmp);

	while (!solved)
	{
		sum=0;
		randomize();

		for (i=1;i<=N;++i)
			sum+= sol[i] ? v[i] : -v[i];
		if (sum==S) break;

		for (i=1;i<=N;++i){
			if (sol[i]){
				s=sum-2*v[i];
			}
			else{
				s=sum+2*v[i];
			}
			if (abs(s-S)<abs(sum-S))
			{
				sol[i]=1-sol[i];
				sum=s;
			}
		}

		if (sum==S) solved=true;
	}

	freopen(OUT,"w",stdout);
	for (i=1;i<=N;++i) printf("%c",sol[i] ? '+' : '-');
	fclose(stdout);

	return 0;
}