Cod sursa(job #1943039)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 28 martie 2017 12:27:30
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.97 kb
#include <bits/stdc++.h>
#define pb push_back
#define NMAX 200050
#define ll long long
#define x first
#define y second
#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int,int> pii;

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

ll v[NMAX];
vector<int> Plus,Minus;
char semn[NMAX];

int main() {
	int n,i,pos;
	ll s,sact=0;

	fin>>n>>s;
	srand(time(NULL));
	for(i=1;i<=n;++i) {
		fin>>v[i];
		if(sact>s) {
			sact-=v[i];
			Minus.pb(i);
			semn[i]='-';
		}
		else {
			sact+=v[i];
			Plus.pb(i);
			semn[i]='+';
		}
	}

	while(sact!=s) {
		if(sact<s) {
			pos=rand()%Minus.size();
			semn[Minus[pos]]='+';
			sact=sact+2*v[Minus[pos]];
			Plus.pb(Minus[pos]);
			Minus[pos]=Minus.back();
			Minus.pop_back();
		}
		else {
			pos=rand()%Plus.size();
			semn[Plus[pos]]='-';
			sact=sact-2*v[Plus[pos]];
			Minus.pb(Plus[pos]);
			Plus[pos]=Plus.back();
			Plus.pop_back();
		}
	}

	fout<<(semn+1);

	return 0;
}