Cod sursa(job #3984)

Utilizator vlad_DVlad Dumitriu vlad_D Data 29 decembrie 2006 22:10:34
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <functional>
#include <sstream>
#include <iostream>
#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;
	}
int main() {
//freopen("semne.in", "r", stdin);
//freopen("semne.out", "w", stdout);
scanf("%lld", &n);
n++;
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;}
	}
srand(time(0)/103);
best = -1;
//for (i=1; i<=maxx; i++) 
while (1)
{
	if (best == -1 || abs2(s1 - s2) < best) {
		best = abs2(s1 -s2);
		bb = neg;
		}
	
	if (s1 == s2) break;
	if (s1 > s2&& 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 (s2 > s1 && 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();
		}
	 if (best == -1 || abs2(s1 - s2) < best) {
		best = abs2(s1 -s2);
		bb = neg;
		}
	}
/*for (i=0; i<bb.size(); i++) {
	printf("%lld\n", 1+bb[i].ind);
	}*/
/*
vector <long long> sol;
for (i=0; i<neg.size(); i++) {
	sol.push_back(1+neg[i].ind);

	//printf("%d\n", 1+neg[i].ind);
	}
sort(sol.begin(), sol.end());
for (i=0; i<sol.size(); i++) {
	printf("%lld\n", sol[i]);
	}
*/
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[1] == 1)  sol[i]*=-1;
		if (sol[i] ==1) printf("+"); else printf("-");}
printf("\n");
}