Cod sursa(job #731381)

Utilizator soriynSorin Rita soriyn Data 7 aprilie 2012 22:49:47
Problema Semne Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#define maxn 50010
using namespace std;

ifstream in("semne.in");
ofstream out("semne.out");

bool vec[maxn];
int neg[maxn],poz[maxn],a[maxn];
int s,n,sneg,spoz,nr,scur;

void read()
{
	std::srand(time(0)); 
	in>>n>>s;
	for(int i=1;i<=n;i++)
	{
		in>>a[i];
		nr=a[i];
		int j=rand()%2;
		if(j==0)
			neg[++neg[0]]=i,scur-=a[i],vec[i]=0;
		else poz[++poz[0]]=i,scur+=a[i],vec[i]=1;
	}
}

void solve()
{

	while(scur!=s)
	{
		if(scur>s)
		{
			int i=rand()%poz[0]+1;
			swap(poz[poz[0]],poz[i]);
			neg[++neg[0]]=poz[poz[0]];
			vec[poz[poz[0]]]=0;
			scur-=2*a[poz[poz[0]]];
			
			--poz[0];
		}
		else if(scur<s)
		{
			int i=rand()%neg[0]+1;
			swap(neg[neg[0]],neg[i]);
			poz[++poz[0]]=neg[neg[0]];
			vec[neg[neg[0]]]=1;
			scur+=2*a[neg[neg[0]]];
			
			--neg[0];
		}
			
	}
	for(int i=1;i<=n;i++)
		if(vec[i]==0) out<<"-";
	     else out<<"+";
}

int main()
{
	read();
	solve();
}