Cod sursa(job #2054498)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 2 noiembrie 2017 00:15:19
Problema Semne Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cstdlib>
using namespace std;

bool find(const vector<pair<int,int> >& v, long long S, vector<int>& sol)
{
	long long sum = 0;
	int left = 0;
	int len = v.size();
	
	for(int i = 0;i < len;++i)
	{
		sum += v[i].first;
		while(sum > S)
		{
			sum -= v[left++].first;
		}
		if(sum == S)
		{
			sol.push_back(left);
			sol.push_back(i);
			return true;
		}
	}
	
	return false;
}

void shuffle(vector<pair<int,int> > & v)
{
	int len = v.size();

	for(int i = len - 1;i >= 0;--i)
	{
		int ind = rand() % (i + 1);
		swap(v[ind], v[i]);
	}
}

int main()
{
	ifstream in("semne.in");
	ofstream out("semne.out");
	
	int N, S;
	in >> N >> S;
	vector<pair<int,int> > v(N);
	
	long long sum = 0;
	for(int i = 0;i < N;++i)
	{
		int nr;
		in >> nr;
		sum += nr;
		v.push_back(make_pair(nr, i));
	}
	long long S1 = (sum - S) / 2;
	
	vector<int> sol;
	while(1)
	{
		bool ret = find(v, S1, sol);
		if(ret)
		{
			break;
		}
		shuffle(v);
	}
	vector<char> ans(N);
	
	for(int i = 0;i < N;++i)
	{
		ans[i] = '+';
	}
	int left = sol[0];
	int right = sol[1];
	
	for(int i = left;i <= right;++i)
	{
		ans[v[i].second] = '-';
	}
	for(int i = 0;i < N;++i)
	{
		out<<ans[i];
	}
	in.close();
	out.close();
}