Cod sursa(job #1225491)

Utilizator kappykkDragos kappykk Data 2 septembrie 2014 17:45:43
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

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

int x[100000];
int Plus[100000];
int Minus[100000];
bool Verif[100000];

int main()
{
    srand(time(0));
    long long n,s;
    long long SumaActuala = 0;
    f>>n;
    f>>s;
    for(int i = 1 ; i <= n ; ++i){
        f>>x[i];
        Plus[++Plus[0]] = i;
        SumaActuala += x[i];
    }
    long long Pozitie;
    while(SumaActuala != s){
        if(SumaActuala == s){
            break;
        }
        if(SumaActuala > s){
            Pozitie = (rand() % Plus[0]) + 1;
            SumaActuala -= 2 * x[Plus[Pozitie]];
            Verif[Plus[Pozitie]] = true;
            Minus[++Minus[0]] = Plus[Pozitie];
            swap(Plus[Pozitie], Plus[Plus[0]]);
            --Plus[0];
        }
        if(SumaActuala < s){
            Pozitie = (rand() % Minus[0]) + 1;
            SumaActuala += 2 * x[Minus[Pozitie]];
            Verif[Minus[Pozitie]] = false;
            Plus[++Plus[0]] = Minus[Pozitie];
            swap(Minus[Pozitie], Minus[Minus[0]]);
            --Minus[0];
        }
    }
        for(int i = 1 ; i <= n ; ++i){
            if(Verif[i])
                g<<"-";
            else
                g<<"+";
        }
    return 0;
}