Cod sursa(job #1942935)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 28 martie 2017 11:56:06
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>
#define pb push_back
#define NMAX 50050
#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];
int Plus[NMAX],Minus[NMAX];
char semn[NMAX];

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

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

	while(s!=sact) {
        if(sact<s) {
            pos=rand()%m+1;
            Plus[++p]=Minus[pos];
            Minus[pos]=Minus[m--];
            semn[Plus[p]]='+';
            sact+=2*v[Plus[p]];
        }
        else {
            pos=rand()%p+1;
            Minus[++m]=Plus[pos];
            Plus[pos]=Plus[p--];
            semn[Minus[m]]='-';
            sact-=2*v[Minus[m]];
        }
    }

	fout<<(semn+1);

	return 0;
}