Cod sursa(job #3136631)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 7 iunie 2023 11:50:33
Problema Semne Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
//Ilie Dumitru
#include<cstdio>
#include<chrono>
#include<map>
#include<random>
const int NMAX=50005;

std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
long long int S, v[NMAX], curr;
int N;
int plus[NMAX], minus[NMAX], cnt[2];
char ans[NMAX];

int main()
{
	//FILE* f=fopen("semne.in", "r"), *g=fopen("semne.out", "w");
	FILE* f=stdin, *g=stdout;
	int i;

	fscanf(f, "%d%lld", &N, &S);
	for(i=0;i<N;++i)
	{
		fscanf(f, "%lld", v+i);
		curr+=v[i];
		plus[cnt[0]++]=i;
	}

	while(curr!=S)
	{
		if(curr<S)
		{
			//schimbam din - in +
			i=std::uniform_int_distribution<int>(0, cnt[1]-1)(rnd);
			curr+=v[minus[i]]<<1;
			plus[cnt[0]++]=minus[i];
			minus[i]=minus[--cnt[1]];
		}
		else
		{
			//schimbam din + in -
			i=std::uniform_int_distribution<int>(0, cnt[0]-1)(rnd);
			curr-=v[plus[i]]<<1;
			minus[cnt[1]++]=plus[i];
			plus[i]=plus[--cnt[0]];
		}
	}

	for(i=0;i<cnt[0];++i)
		ans[plus[i]]='+';
	for(i=0;i<cnt[1];++i)
		ans[minus[i]]='-';
	fprintf(g, "%s\n", ans);

	fclose(f);
	fclose(g);
	return 0;
}