Cod sursa(job #802025)

Utilizator Marius96Marius Gavrilescu Marius96 Data 25 octombrie 2012 18:11:26
Problema Semne Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<vector>

std::vector<int> gm;
std::vector<int> gp;

long long v[50005];
char str[400000];
int n;

int main()
{
	srand (time (NULL));
	freopen ("semne.in","r",stdin);
	freopen ("semne.out","w",stdout);

	long long s,c=0;
//	scanf ("%d%lld\n",&n,&s);
	gets (str);
	n=atoi (str);
	s=atoll (strchr (str,' ')+1);
	gets (str);

	char *ss=strtok (str," ");
	for(int i=0;i<n;i++){
		v[i]=atoi (ss);
		ss=strtok (NULL," ");
		if(c<s)
			c+=v[i],gp.push_back (i);
		else
			c-=v[i],gm.push_back (i);
	}

	while(s!=c){
		if(c<s){
			int r=((rand()>>16)+rand())%gm.size();
			int val=gm[r];
			gp.push_back (val);
			c+=2*v[val];
			gm.erase (gm.begin()+r);
		} else {
			int r=((rand()>>16)+rand())%gp.size();
			int val=gp[r];
			gm.push_back (val);
			c-=2*v[val];
			gp.erase (gp.begin()+r);
		}
	}

	str[n]=0;
	for(std::vector<int>::iterator it=gm.begin();it!=gm.end();it++)
		str[*it]='-';
	for(std::vector<int>::iterator it=gp.begin();it!=gp.end();it++)
		str[*it]='+';
	puts (str);

	return 0;
}