Cod sursa(job #4193)

Utilizator vlad_DVlad Dumitriu vlad_D Data 31 decembrie 2006 23:21:37
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <time.h>
#define maxx 1000
using namespace std;

struct per{long long val, ind;};

long long n, i, j, best;
long long s1= 0, s2= 0,  pos;

vector <per> poz, neg;
vector <per> bb;
long long abs2 (long long B) {
	if (B < 0) return -B;
	return B;
	}
long long S;
int main() {
freopen("semne.in", "r", stdin);
freopen("semne.out", "w", stdout);
scanf("%lld", &n);
srand(time(0)/123);
	scanf("%lld", &S);
for (i=0; i<n; i++) {
	int X;
	scanf("%lld", &X);
	per A;
	A.val = X; A.ind = i;
	if (rand()%2 == 0) {
	poz.push_back(A);
	s1+=X;}
	else {neg.push_back(A); s2+=X;}
	}

best = -1;
//for (i=1; i<=maxx; i++) 
while (1)
{	if (s1 - s2 == S) break;

	if (s1 - s2 > S&& poz.size()>0) {
		pos = rand()%poz.size();
		s1-=poz[pos].val;
		s2+=poz[pos].val;
		neg.push_back(poz[pos]);
    	        poz[pos] = poz[poz.size()-1]; poz.pop_back();
		}
	 if (s1 -s2 <S && neg.size() >0){
		pos = rand()%neg.size();
		s1+=neg[pos].val;
		s2-=neg[pos].val;
		poz.push_back(neg[pos]);
		neg[pos] = neg[neg.size()-1]; neg.pop_back();
		}

	}
int sol[50010];
for (i=0; i<poz.size(); i++) sol[poz[i].ind+1] =  1;
for (i=0; i<neg.size(); i++) sol[neg[i].ind+1] = -1;
for (i=2; i<=n; i++) {
		if (sol[i] ==1) printf("+"); else printf("-");}
printf("\n");
}