Cod sursa(job #1070278)

Utilizator assa98Andrei Stanciu assa98 Data 31 decembrie 2013 15:34:37
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;

const int MAX_N=50100;

vector<int> plus;
vector<int> minus;

int v[MAX_N];
bool semn[MAX_N];

int main() {
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    srand(time(0));

    long long s,sum=0;
    int n;
    scanf("%d%lld",&n,&s);
    for(int i=1;i<=n;i++) {
        scanf("%d",&v[i]);
        semn[i]=rand()&1;
        if(semn[i]) {
            plus.push_back(i);
            sum+=v[i];
        }
        else {
            minus.push_back(i);
            sum-=v[i];
        }
    }

    while(sum!=s) {
        if(sum>s) {
            int poz=rand()%plus.size();
            semn[plus[poz]]=false;
            sum-=2*v[plus[poz]];
            minus.push_back(plus[poz]);
            swap(plus[poz],plus[plus.size()-1]);
            plus.pop_back();
        }
        else if(sum<s) {
            int poz=rand()%minus.size();
            semn[minus[poz]]=true;
            sum+=2*v[minus[poz]];
            plus.push_back(minus[poz]);
            swap(minus[poz],minus[minus.size()-1]);
            minus.pop_back();
        }
    }

    for(int i=1;i<=n;i++) {
        if(semn[i]) {
            printf("+");
        }
        else {
            printf("-");
        }
    }
    return 0;
}