Cod sursa(job #2513645)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 23 decembrie 2019 16:10:15
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda temadec2019 Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

main()
{
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	int n;
	long long sum;
	fin >> n >> sum;
	
	vector <char> sign(n, '+');
	vector <int> v(n);
	
	vector <int> p0;
	vector <int> p1;

	for(int i = 0; i < n; i++)
	{
		fin >> v[i];
		
		p1.push_back(i);
		sum -= v[i];
	}
	
	while(sum != 0)
	{
		if(sum < 0)
		{
			int pos = uniform_int_distribution<int> (0, p1.size() - 1)(rng);
			
			sum += 2 * v[p1[pos]];
			
			sign[p1[pos]] = '-';
			
			p0.push_back(p1[pos]);
			swap(p1[p1.size() - 1], p1[pos]);
			p1.pop_back();
		}
		else
		{
			int pos = uniform_int_distribution<int> (0, p0.size() - 1)(rng);
			
			sum -= 2 * v[p0[pos]];
			
			sign[p0[pos]] = '+';
			
			p1.push_back(p0[pos]);
			swap(p0[p0.size() - 1], p0[pos]);
			p0.pop_back();
		}
	}
	
	for(auto i : sign)
		fout << i;
}