Cod sursa(job #1428279)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 3 mai 2015 23:36:00
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct treap {
    int val, pr;
    int sz;

    treap *l, *r;

    treap (int val = 0, int pr = 0, int sz = 0, treap *l = NULL, treap *r = NULL): val(val), pr(pr), sz(sz), l(l), r(r) {}
} *root, *nil;

inline void calc_sz (treap *t) {
    if (t != nil)
        t -> sz = 1 + t -> l -> sz + t -> r -> sz;
}

void split (treap *t, int k, treap* &l, treap* &r) {
    if (t == nil) {
        l = r = nil;
        return ;
    }

    if (k <= t -> l -> sz) {
        split(t -> l, k, l, t -> l);
        r = t;

        calc_sz(l);
        calc_sz(r);
    }
    else {
        split(t -> r, k - t -> l -> sz - 1, t -> r, r);
        l = t;

        calc_sz(l);
        calc_sz(r);
    }
}

void merge (treap* &t, treap* l, treap* r) {
    if (l == nil) {
        t = r;
        return ;
    }
    else if (r == nil) {
        t = l;
        return ;
    }

    if (l -> pr < r -> pr) {
        merge(r -> l, l, r -> l);
        t = r;
    }
    else {
        merge(l -> r, l -> r, r);
        t = l;
    }

    calc_sz(t);
}

void ins (treap* &t, int val, int pr, int k) {
    if (pr > t -> pr) {
        treap *l = new treap(val, pr);
        split(t, k - 1, l -> l, l -> r);

        t = l;
        calc_sz(t);

        return ;
    }

    if (k <= t -> l -> sz + 1)
        ins(t -> l, val, pr, k);
    else
        ins(t -> r, val, pr, k - t -> l -> sz - 1);

    calc_sz(t);
}

int erase (treap* &t, int k) {
    int ans = 0;

    if (k <= t -> l -> sz)
        ans = erase(t -> l, k);
    else if (k == t -> l -> sz + 1) {
        treap *l = t;
        int aux = l -> val;

        merge(t, t -> l, t -> r);
        calc_sz(t);

        delete l;

        return aux;
    }
    else
        ans = erase(t -> r, k - t -> l -> sz - 1);

    calc_sz(t);
    return ans;
}

/*void dfs (treap *t) {
    if (t == nil) {
        cout << "nil" << endl;
        return ;
    }

    cout << "STANGA " << endl;
    dfs(t -> l);
    cout << "SUS" << endl;

    cout << t -> val << ' ' << t -> sz << endl;

    cout << "DREAPTA" << endl;
    dfs(t -> r);
    cout << "SUS" << endl;
}*/

int main()
{
    ifstream cin("order.in");
    ofstream cout("order.out");

    srand(time(0));

    nil = new treap(-1, -1);
    nil -> l = nil -> r = nil;
    root = nil;

    int n = 0;
    cin >> n;

    for (int i = 1; i <= n; i++)
        ins(root, i, rand(), i);

    int pos = 2;
    for (int i = 1; i <= n; i++) {
        pos += (i - 1);
        pos = (pos - 1) % (n - i + 1) + 1;

        cout << erase(root, pos) << " \n"[i == n];
    }

    cin.close();
    cout.close();
    return 0;
}