Cod sursa(job #1735534)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 30 iulie 2016 07:15:13
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
///Promit ca o sa bag si un algoritm genetic pe acest jeg
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int NMAX = 50005;

int n;
i64 s, t; ///Sum, target

vector<int> add, drop;
char        ant[NMAX]; ///Antwort
int           v[NMAX];

int main(void) {
    freopen("semne.in",  "r", stdin);
    freopen("semne.out", "w", stdout);
    int pos;

    scanf("%d%lld",&n,&t);
    for(int i=0; i<n; ++i) {
        scanf("%d",&v[i]);
        if(v[i]+s<=t) {
            add.push_back(i);
            s += v[i];
        }
        else {
            drop.push_back(i);
            s -= v[i];
        }
    }

    while(s!=t) {
        if(s > t) {
            pos = rand() % add.size();
            s  -= 2 * v[add[pos]];
            drop.push_back(add[pos]);
            add[pos] = add.back();
            add.pop_back();
        }
        else {
            pos = rand() % drop.size();
            s  += 2 * v[drop[pos]];
            add.push_back(drop[pos]);
            drop[pos] = drop.back();
            drop.pop_back();
        }
    }

    for(auto i:add)
        ant[i] = '+';
    for(auto i:drop)
        ant[i] = '-';

    printf("%s\n",ant);

    fclose(stdin);
    fclose(stdout);
    return 0;
}