Cod sursa(job #786277)

Utilizator cosminx2003Cosmin Clapon cosminx2003 Data 10 septembrie 2012 20:37:04
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdlib>
#include <ctime>
#include <fstream>
#define N 50000

using namespace std;

ifstream f("semne.in");
ofstream g("semne.out");

char output[N];
int v[N],pls[N],mns[N];

int main() {
	int i,n,p = 0,m = 0,r;
	long long s,c = 0;

	srand(time(NULL));
	f>>n>>s;
	for(i = 0; i < n; i++)
		f>>v[i];
	
	for(i = 0; i < n; i++) {
		if(rand()%2) {
			pls[p++] = i;
			c += v[i];
			output[i] = '+';
		} else {
			mns[m++] = i;
			c -= v[i];
			output[i] = '-';
		}
	}

	while(s != c) {
		if(c < s) {
			r = rand()%m;
			c += (long long)v[mns[r]]<<1;
			output[mns[r]] = '+';
			pls[p++] = mns[r];
			mns[r] = mns[--m];
		} else {
			r = rand()%p;
			c -= (long long)v[pls[r]]<<1;
			output[pls[r]] = '-';
			mns[m++] = pls[r];
			pls[r] = pls[--p];
		}
	}

	g<<output;

	return 0;
}