Cod sursa(job #801565)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 24 octombrie 2012 18:16:38
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>

using namespace std;

long long n, s, sc, vrs[50050], isg[50050];
vector<int> ng, pz;

int main(){
	freopen("semne.in" ,"r", stdin);
	freopen("semne.out", "w", stdout);
	
	srand(time(0));
	scanf("%lld%lld", &n, &s);
	for(int i = 0; i < n; ++i)
		scanf("%lld", &vrs[i]);
		
	for(int i = 0; i < n; ++i)
		if(rand() % 2){
			sc -= vrs[i];
			isg[i] = -1;
			ng.push_back(i);
		}
		else{
			sc += vrs[i];
			isg[i] = 1;
			pz.push_back(i);
		}
	
	while(sc != s){
		if(sc > s){
			int ind = rand() % pz.size();
			swap(pz[ind], pz[pz.size() - 1]);
			ng.push_back(pz.back());
			sc -= 2 * vrs[pz.back()];
			isg[pz.back()] = -1;
			pz.pop_back();
		}
		else{
			int ind = rand() % ng.size();
			swap(ng[ind], ng[ng.size() - 1]);
			pz.push_back(ng.back());
			sc += 2 * vrs[ng.back()];
			isg[ng.back()] = 1;
			ng.pop_back();
		}
	}
	
	for(int i = 0; i < n; ++i)
		if(isg[i] == 1)
			printf("+");
		else
			printf("-");
	return 0;
}