Cod sursa(job #1943428)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 28 martie 2017 16:27:49
Problema Semne Scor 100
Compilator cpp Status done
Runda 28-03-2017_todo Marime 1.21 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;
}