Cod sursa(job #748955)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 15 mai 2012 11:17:27
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<iostream>
#include<fstream>
#include<ctime>
#include<stdlib.h>
using namespace std;

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

const int N = 50010;

long long n, su, x[N], s[N], d[N], rez[N], ls, ld, r, sum;

int main() {
    int i;

    in >> n >> su;

    srand(time(NULL));

    for(i = 1; i<=n; ++i) {
        in >> x[i];

        r = rand()&1;

        if(r) {

            s[++ls] = i;
            sum += x[i];
            rez[i] = 1;
        }
        else {
            d[++ld] = i;
            sum -= x[i];
        }
    }

    while(sum!=su) {

        if(sum > su) {
            r = rand()%ls + 1;

            sum -= 2*x[s[r]];
            d[++ld] = s[r];
            s[r] = s[ls--];
            rez[d[ld]] = 0;
        }
        else if(sum < su) {
            r = rand()%ld + 1;

            sum += 2*x[d[r]];
            s[++ls] = d[r];
            d[r] = d[ld--];
            rez[s[ls]] = 1;
        }
    }

    for(i = 1; i<=n; ++i) {
        if(rez[i])
            out << '+';
        else
            out << '-';
    }

    return 0;
}