Cod sursa(job #1626758)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 3 martie 2016 11:46:12
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <fstream>
#define MOD 105011
#define NMAX 30005
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

//FILE *fin = freopen("schi.in", "r", stdin);
//FILE *fout = freopen("schi.out", "w", stdout);

ifstream fin("schi.in");
ofstream fout("schi.out");

typedef pair<int, int> pii;

int v[NMAX];
pii clasament[NMAX];
short ai[4 * NMAX];
int n, qst, qdr, ansQ, pozUpdate;

inline void build(int nod, int st, int dr) {
    if (st == dr) {
        ai[nod] = 1;
        return;
    }

    int mid = (st + dr) >> 1, fs = (nod << 1);
    build(fs, st, mid);
    build(fs + 1, mid + 1, dr);

    ai[nod] = ai[fs] + ai[fs + 1];
}

inline void query(int nod, int st, int dr) {
    if (dr<qst || st>qdr)
        return;

    if (qst <= st && qdr >= dr) {
        ansQ += ai[nod];
        return;
    }

    int mid = (st + dr) >> 1, fs = (nod << 1);
    if (qst <= mid)
        query(fs, st, mid);
    if (mid < qdr)
        query(fs + 1, mid + 1, dr);
}

inline void update(int nod, int st, int dr) {
    if (st == dr) {
        ai[nod] = 0;
        return;
    }

    int mid = (st + dr) >> 1, fs = (nod << 1);
    if (pozUpdate <= mid)
        update(fs, st, mid);
    else
        update(fs + 1, mid + 1, dr);

    --ai[nod];
}

inline int binSearch(int x) {
    int st, dr, mid, res;

    st = 1;
    dr = n;
    while (st <= dr) {
        mid = (st + dr) >> 1;

        qst = 1;
        qdr = mid;
        ansQ = 0;
        query(1, 1, n);
        if (ansQ == x)
            res = mid;

        if (ansQ < x)
            st = mid + 1;
        else
            dr = mid - 1;
    }

    return res;
}

int main() {
    int i, poz, aux;

    fin>>n;

    for (i = 1; i <= n; ++i)
        fin>>v[i];

    build(1, 1, n);
    for (i = n; i > 0; --i) {
        poz = binSearch(v[i]);
        clasament[i].first = poz;
        clasament[i].second = i;
        pozUpdate = poz;
        update(1, 1, n);
    }

    sort(clasament + 1, clasament + n + 1);
    for (i = 1; i <= n; ++i)
        fout<<clasament[i].second<<'\n';

    return 0;
}