Cod sursa(job #2307755)

Utilizator mirunazMiruna Zavelca mirunaz Data 25 decembrie 2018 17:00:29
Problema Schi Scor 95
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <stdlib.h>

void modify(int v[], int n, int p, int value)
{
    while (p <= n)
    {
        v[p] += value;
        p += (p&(p^(p-1)));
    }
}

int binarySearch(_Bool a[], int v[], int n, int s)
{
    int i, step = 1;
    while (step < n)
        step <<= 1;
    for (i=0; step; step>>=1) {
        if (i + step <= n && v[i + step] <= s) {
            i += step;
            s -= v[i];
            if (s == 0) {
                while (a[i] == 0) {
                    i--;
                }
                a[i] = 0;
                return i;
            }
        }
    }
    return -1;
}

int main() {
    int i, n;
    FILE *in = fopen("schi.in", "r");
    FILE *out = fopen("schi.out", "w");
    fscanf(in, "%d", &n);
    int v[n+1], aib[n+1], w[n+1];
    _Bool a[n+1];
    for(i=1; i<=n; i++) {
        fscanf(in, "%d", &w[i]);
        aib[i] = 0;
        a[i] = 1;
    }

    for(i=1; i<=n; i++) {
        modify(aib, n, i, 1);
    }

    int x;
    for(i=n; i>=1; i--) {
        x = binarySearch(a, aib, n, w[i]);
        v[x] = i;
        //printf("%d\n", x);
        modify(aib, n, x, -1);
    }

    for(i=1; i<=n; i++) {
        fprintf(out, "%d\n", v[i]);
    }

    fclose(in);
    fclose(out);
    return 0;
}