Cod sursa(job #1735538)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 30 iulie 2016 07:21:12
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 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;

class hpstream {
private:
    static const int BMAX = 1<<17;

    FILE *file;
    int   buff;
    char  str[BMAX];

    inline char nextch(void) {
        if(buff==BMAX) {
            fread(str, 1, BMAX, file);
            buff = 0;
        }
        return str[buff++];
    }

public:
    hpstream() {}
    hpstream(const char *str) {
        file = fopen(str, "r");
        buff = BMAX;
    }

    inline hpstream &operator>> (int &arg) {
        char ch, sgn=1;

        arg = 0;

        while(!isdigit(ch=nextch()) && ch!='-');

        if(ch=='-') {
            sgn=-1;
            ch=nextch();
        }
        arg=ch-'0';
        while(isdigit((ch=nextch())))
            arg=arg*10+ch-'0';

        arg*=sgn;

        return *this;
    }

    inline hpstream &operator>> (i64 &arg) {
        char ch, sgn=1;

        arg = 0;

        while(!isdigit(ch=nextch()) && ch!='-');

        if(ch=='-') {
            sgn=-1;
            ch=nextch();
        }
        arg=ch-'0';
        while(isdigit((ch=nextch())))
            arg=arg*10+ch-'0';

        arg*=sgn;

        return *this;
    }

    void close(void) {
        fclose(file);
    }
};

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

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

int main(void) {
    hpstream f("semne.in");
    ofstream g("semne.out");
    int pos;

    srand(time(NULL)); /// :)))) (M-am prins cam greu ca nimeni nu are atat ghinion)

    f>>n>>t;
    for(int i=0; i<n; ++i) {
        f>>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] = '-';

    g<<ant<<'\n';

    f.close();
    g.close();
    return 0;
}