Cod sursa(job #734820)

Utilizator vendettaSalajan Razvan vendetta Data 14 aprilie 2012 22:16:43
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
#define nmax 50005

using namespace std;

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

int n, a[nmax], Plus[nmax], Minus[nmax], nr_p, nr_m;
char rez[nmax];
long long s, s2=0;

void citeste(){

    f >> n >> s;
    for(int i=1; i<=n; i++){
        f >> a[i];
        int x = rand()%2;

        if (x){
            Plus[++nr_p] = i;
            s2 += a[i]*1LL;
            rez[i] = '+';
        }else {
            Minus[++nr_m] = i;
            s2 -= a[i]*1LL;
            rez[i] = '-';
        }
    }

}

void rezolva(){


    for(; s2 != s; ){
        if (s2 < s){//daca suma act e mai mica atunci modific un minus in plus
            int x = rand()%nr_m+1;
            Plus[++nr_p] = Minus[x];
            Minus[x] = Minus[nr_m];
            --nr_m;
            s2 += 1LL*2*a[ Plus[nr_p] ];//adaug la suma de 2 ori valoarea(fiindca inainte l`am scazut)
            rez[ Plus[nr_p] ] = '+';
        }else {
            int x = rand()%nr_p+1;
            Minus[++nr_m] = Plus[x];
            Plus[x] = Plus[nr_p];
            --nr_p;
            s2 -= 1LL*2*a[ Minus[nr_m] ];
            rez[ Minus[nr_m] ] = '-';
        }
    }

}

void scrie(){

    for(int i=1; i<=n; i++) g << rez[i];
    g << "\n";

}

int main(){

    srand((unsigned)time(NULL));

    citeste();
    rezolva();
    scrie();

    f.close();
    g.close();

    return 0;

}