Cod sursa(job #806055)

Utilizator dariusdariusMarian Darius dariusdarius Data 1 noiembrie 2012 19:14:29
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
long long n, s, ss, v[50050], semn[50050];
int i;
vector<int> m, p;
int main()
{
	freopen("semne.in" ,"r", stdin);
	freopen("semne.out", "w", stdout);
	srand(time(0));
	scanf("%lld%lld", &n, &s);
	for(i=1;i<=n;i++)
		scanf("%lld", &v[i]);
	for(i=1;i<=n;i++)
		if(rand()%2)
		{
			ss-=v[i];
			semn[i]=-1;
			m.push_back(i);
		}
		else
		{
			ss += v[i];
			semn[i] = 1;
			p.push_back(i);
		}
	
	while(ss != s)
		if(ss > s)
		{
			int ind = rand() % p.size();
			swap(p[ind], p[p.size() - 1]);
			m.push_back(p.back());
			ss -= 2 * v[p.back()];
			semn[p.back()] = -1;
			p.pop_back();
		}
		else
		{
			int ind = rand() % m.size();
			swap(m[ind], m[m.size() - 1]);
			p.push_back(m.back());
			ss += 2 * v[m.back()];
			semn[m.back()] = 1;
			m.pop_back();
		}
	
	for(i=1;i<=n;i++)
		if(semn[i] == 1)
			printf("+");
		else
			printf("-");
	return 0;
}