Cod sursa(job #2654272)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 30 septembrie 2020 13:20:28
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb

#include <bits/stdc++.h>

using namespace std;

ifstream f ("order.in");
ofstream g ("order.out");

struct nod {
    nod *st, *dr;

    int prior;
    int val;
    int sz;

    bool R;
};

nod nil;

nod *Reverse (nod *T) {
    swap(T->st, T->dr);

    T->R = !T->R;

    return T;
}

nod *Propag (nod *T) {
    if (T != &nil && T->R) {
        T->st = Reverse(T->st);
        T->dr = Reverse(T->dr);
        T->R = 0;
    }

    return T;
}

nod *mod_fiu (nod *T, int care, nod *fiu) {
    if (care == 0) T->st = fiu;
    else T->dr = fiu;

    T->sz = T->st->sz + 1 + T->dr->sz;

    return T;
}

nod *join (nod *st, nod *dr) {
    st = Propag(st);
    dr = Propag(dr);
    if (st == &nil) return dr;
    if (dr == &nil) return st;

    if (st->prior >= dr->prior) {
        return mod_fiu(st, 1, join(st->dr, dr));
    }
    else return mod_fiu(dr, 0, join(st, dr->st));
}

pair <nod*, nod*> split (nod *T, int k) {
    T = Propag(T);
    if (T == &nil) return make_pair(&nil, &nil);

    if (T->st->sz >= k) {
        auto t = split(T->st, k);

        return make_pair(t.first, mod_fiu(T, 0, t.second));
    }
    else {
        auto t = split(T->dr, k - T->st->sz - 1);

        return make_pair(mod_fiu(T, 1, t.first), t.second);
    }
}

nod *Adaug (nod *T, int poz, int val) {
    T = Propag(T);
    pair <nod*, nod*> S = split(T, poz);

    nod *now = new nod;
    *now = nod{&nil, &nil, rand(), val, 1, 0};

    return join(join(S.first, now), S.second);
}

int Acces (nod *T, int poz) {
    T = Propag(T);
    auto t = split(T, poz+1);
    auto t_ = split(t.first, poz);

    T = join(join(t_.first, t_.second), t.second);

    return t_.second->val;
}

nod *Invers (nod *T, int x, int y) {
    T = Propag(T);
    auto t = split(T, y+1);
    auto t_ = split(t.first, x);

    t_.second = Reverse(t_.second);

    return join(join(t_.first, t_.second), t.second);
}

nod *Delete (nod *T, int x, int y) {
    T = Propag(T);
    auto t = split(T, y+1);
    auto t_ = split(t.first, x);

    return join(t_.first, t.second);
}

int main()
{
    srand(time(NULL));
    int N;
    f >> N;

    nod *T = &nil;

    for (int i = 3; i <= N; ++ i ) {
        T = Adaug(T, i-3, i);
    }

    T = Adaug(T, N-2, 1);

    g << 2 << " ";

    for (int i = 2; i <= N; ++ i ) {
        int cate = i % T->sz;
        if (cate == 0) cate = T->sz;

        int val = Acces(T, cate - 1);

        g << val << " ";

        T = Delete(T, i-1, i-1);
        T = Invers(T, 0, T->sz-1);
        T = Invers(T, 0, T->sz-i);
        T = Invers(T, T->sz-i+1, T->sz-1);
    }

    return 0;
}