Cod sursa(job #2390964)

Utilizator alexge50alexX AleX alexge50 Data 28 martie 2019 16:15:54
Problema Schi Scor 70
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
/*
 * NVIDIA, Fuck you!
 *      - Linux Torvalds
 */

#include <stdio.h>

#define MAX_N 30000
#define MAX_NODES (32768 * 2 - 1)

int v[MAX_N];
int aint[MAX_NODES];
int r[MAX_N + 1];

void set(int n, int x, int node, int l, int r)
{
    if(l == r)
    {
        aint[node] = x;
        return;
    }

    int middle = (l + r) / 2;

    if(n <= middle)
        set(n, x, 2 * node, l, middle);
    else set(n, x, 2 * node + 1, middle + 1, r);

    aint[node] = aint[2 * node] + aint[2 * node + 1];
}

void increment(int n, int node, int l, int r)
{
    if(l == r)
    {
        aint[node] ++;
        return;
    }

    int middle = (l + r) / 2;

    if(n <= middle)
        increment(n, 2 * node, l, middle);
    else increment(n, 2 * node + 1, middle + 1, r);

    aint[node] = aint[node * 2] + aint[node * 2 + 1];
}

int query(int a, int b, int node, int l, int r )
{
    if(a <= l && r <= b)
        return aint[node];

    int middle = (l + r) / 2;
    int max = 0;

    if(a <= middle)
        max = query(a, b, 2 * node, l, middle);
    if(b > middle)
        max =
                max +
                query(a, b, 2 * node + 1, middle + 1, r);

    return max;
}

int main()
{
    FILE *fin, *fout;
    int n;

    fin = fopen("schi.in", "r");

    fscanf(fin, "%d", &n);
    for(int i = 0; i < n; i++)
        fscanf(fin, "%d", &v[i]);
    fclose(fin);


    for(int i = n - 1; i >= 0; i--)
    {
        int x;
        int last = 1, last_x = 0;

        while((x = query(1, v[i], 1, 1, n)) != last_x)
            v[i] += (x - last_x), last_x = x;

        increment(v[i], 1, 1, n);
    }

    for(int i = 0; i < n; i++)
        r[v[i]] = i + 1;

    fout = fopen("schi.out", "w");

    for(int i = 1; i <= n; i ++)
        fprintf(fout, "%d\n", r[i]);

    fclose(fout);

}