Cod sursa(job #2108084)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 17 ianuarie 2018 21:26:35
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <bits/stdc++.h>
#define MAXN 50000

typedef struct Treap* Tree;
typedef std::pair <Tree, Tree> PTT;
Tree NIL;
struct Treap{
    int val;
    int priority = rand();
    int sub = 1;
    bool lazy;
    Tree st = NIL, dr = NIL;

    Treap(int nval = 0){val = nval;}
    ~Treap(){if(st != NIL) delete st; if(dr != NIL) delete dr;}
};

void reset(Tree T){
    T -> sub = 1 + T -> st -> sub + T -> dr -> sub;
}

void propagate(Tree T){
    if(T == NIL) return;
    if(T -> lazy){
        std::swap(T -> st, T -> dr);
        T -> st -> lazy ^= 1;
        T -> dr -> lazy ^= 1;
        T -> lazy = 0;
    }
}

int access(Tree T, int pos){
    propagate(T);
    if(T == NIL)
        return -1;
    if(pos <= T -> st -> sub)
        return access(T -> st, pos);
    else if(pos == T -> st -> sub + 1)
        return T -> val;
    else
        return access(T -> dr, pos - T -> st -> sub - 1);
}

Tree join(Tree A, Tree B){
    if(A == NIL) return B;
    if(B == NIL) return A;
    propagate(A);propagate(B);

    if(A -> priority >= B -> priority){
        A -> dr = join(A -> dr, B);
        reset(A);
        return A;
    }
    else{
        B -> st = join(A, B -> st);
        reset(B);
        return B;
    }
}

PTT split(Tree T, int pos){
    if(T == NIL) return {NIL, NIL};
    propagate(T);

    if(pos <= T -> st -> sub){
        PTT S = split(T -> st, pos);
        T -> st = S.second;
        reset(T);
        return {S.first, T};
    }
    else if(pos == T -> st -> sub + 1){
        PTT S = {T -> st, T};
        T -> st = NIL;
        reset(T);
        return S;
    }
    else{
        PTT S = split(T -> dr, pos - 1 - T -> st -> sub);
        T -> dr = S.first;
        reset(T);
        return {T, S.second};
    }
}

Tree insert(Tree T, int val, int pos){
    Tree newT = new Treap(val);
    PTT S = split(T, pos);
    return join(S.first, join(newT, S.second));
}
Tree erase(Tree T, int st, int dr){
    PTT x = split(T, dr + 1);
    PTT y = split(x.first, st);
    if(y.second != NIL) delete y.second;
    return join(y.first, x.second);
}

long long v[1 + MAXN];
int f[1 + MAXN];
int main(){
    FILE*fi,*fo;
    fi = fopen("semne.in","r");
    fo = fopen("semne.out","w");

    srand(time(NULL));
    NIL = new Treap();
    NIL -> st = NIL -> dr = NIL;
    NIL -> sub = 0;
    Tree P = NIL;
    Tree Q = NIL;

    int N;
    long long s;
    fscanf(fi,"%d%lld", &N, &s);
    for(int i = 1; i <= N; i++)
        fscanf(fi,"%lld", &v[i]);
    long long sum = 0;
    int p, n;
    for(int i = 1; i <= N; i += 2){
        f[i] = 1;
        P = insert(P, i, 1);
        p++;
        sum += v[i];
    }
    for(int i = 2; i <= N; i += 2){
        f[i] = -1;
        Q = insert(Q, i, 1);
        n++;
        sum -= v[i];
    }

    while(sum != s){
        int i, j = 1, con = 0;
        if(sum > s){
            i = 1 + rand() % p;
            p--;
            n++;
            j = access(P, i);
            P = erase(P, i, i);
            Q = insert(Q, j, 1);
        }
        else{
            i = 1 + rand() % n;
            p++;
            n--;
            j = access(Q, i);
            Q = erase(Q, i, i);
            P = insert(P, j, 1);
        }
        sum -= f[j] * v[j];
        f[j] = -f[j];
        sum += f[j] * v[j];
    }
    for(int i = 1; i <= N; i++)
        if(f[i] == 1) fprintf(fo,"+");
        else fprintf(fo,"-");

    return 0;
}