Cod sursa(job #521636)

Utilizator klamathixMihai Calancea klamathix Data 12 ianuarie 2011 23:35:31
Problema Semne Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<fstream>
#include<cstdlib>
#include<ctime>
using namespace std;
const int maxn = 50005;

int i , j , tip , pluss[maxn] , minuss[maxn] , n , m , ind , v[maxn];
long long int sum , s , nr , uplim = 1000000000000000000LL , downlim = -100000000000000000LL;
bool is[maxn];

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

int main()
{
	srand(time(0));
	
	fin >> nr >> s;
	for( i = 1 ; i <= nr ; ++i ) {
		fin >> v[i];
		tip = rand() % 2;
		if ( tip ) 
			minuss[++n] = i , sum -= v[i];
		else
			pluss[++m] = i , sum += v[i];
	}
	
	for ( ; 1 ; ) {
		if ( sum == s ) break;
		
		if ( sum > s ) {
			sum -= 2 * v[pluss[ind]];
			minuss[++n] = pluss[ind];
			pluss[ind] = pluss[m--];
		}
		else {
				ind = rand() % m + 1;
			ind = rand() % n + 1;
			sum += 2 * v[minuss[ind]];
			pluss[++m] = minuss[ind];
			minuss[ind] = minuss[n--];
		}
	}
	
	for( i = 1 ; i <= m ;  ++i )
		is[pluss[i]] = true;
	for( i = 1 ; i <= nr ; ++i )
		if (is[i])
			fout<<"+";
		else
			fout<<"-";
		
	fout <<"\n";
	return 0;
}