Cod sursa(job #2327855)

Utilizator shantih1Alex S Hill shantih1 Data 25 ianuarie 2019 01:46:07
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;
ifstream fin("semne.in");
ofstream fout("semne.out");

int n,i,j,p,x,a;
int v[50005];
long long s,S;

struct vec
{	int v;
	char s;
	bool operator<(const vec &sec)const
	{	return v<sec.v;	}
} doi[50005];

int main() {
	
	srand(unsigned(time(0)));
	
	fin>>n>>S;
	for(i=1;i<=n;i++)
		fin>>v[i];
	
	p=n-n/8;
	for(i=1;i<=n-n/8;i++)
		s-=v[i];
	for(i=n-n/8+1;i<=n;i++)
		s+=v[i];
	
	while(s!=S)
	{
		if(s<S && p)
		{
			x=rand()%p+1;
			s+=2*v[x];
			a=v[x];	v[x]=v[p]; v[p]=a;
			p--;
		}
		if(s>S && p<n)
		{
			x=p+rand()%(n-p)+1;
			s-=2*v[x];
			p++;
			a=v[x];	v[x]=v[p];	v[p]=a;
		}
	}
	for(i=1;i<=n;i++)
	{
		doi[i].v=v[i];
		doi[i].s=(i<=p)?'-':'+';
	}
	sort(doi+1,doi+n+1);
	
	for(i=1;i<=n;i++)
		fout<<doi[i].s;
}