Cod sursa(job #345435)

Utilizator Mishu91Andrei Misarca Mishu91 Data 2 septembrie 2009 23:28:20
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.98 kb
#include <cstdio>
#include <vector>
#include <bitset>

using namespace std;

#define MAX_N 50005

int N, V[MAX_N];
long long S, T;
bitset <MAX_N> Semn;
vector <int> P, M;

void citire()
{
	scanf("%d %lld",&N, &S);
	
	for(int i = 1; i <= N; ++i)
	{
		scanf("%d",V+i);
		
		if(T+V[i] > S)
		{
			M.push_back(i);
			Semn[i] = 0;
			T -= V[i];
		}
		
		else
		{
			P.push_back(i);
			Semn[i] = 1;
			T += V[i];
		}
	}
}

void solve()
{
	srand(time(NULL));
	while(T != S)
	{
		if(T > S)
		{
			int poz = rand() % P.size();
			int act = P[poz];
			T -= V[act]*2;
			P[poz] = P[P.size() - 1];
			P.pop_back();
			M.push_back(act);
			Semn[act] = 0;
		}
		else
		{
			int poz = rand() % M.size();
			int act = M[poz];
			T += V[act]*2;
			M[poz] = M[M.size() - 1];
			M.pop_back();
			P.push_back(act);
			Semn[act] = 1;
		}
	}
		
	for(int i = 1; i <= N; ++i)
		printf("%c",(Semn[i] == 0)? '-' : '+');
}

int main()
{
	freopen("semne.in","rt",stdin);
	freopen("semne.out","wt",stdout);
	
	citire();
	solve();
}