Cod sursa(job #2301272)

Utilizator mihaicivMihai Vlad mihaiciv Data 12 decembrie 2018 19:59:57
Problema Schi Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <stdlib.h>

int getFreePlace(int node, int left, int right, int value, int *sgmTree) {
    if (left == right) {
        return left;
    } else {
        int mid = (left + right ) / 2;
        int emptySeats = mid - left + 1 - sgmTree[2 * node]; /// left free seats
        if (emptySeats >= value) {
            return getFreePlace(2 * node, left, mid, value, sgmTree);
        } else {
            return getFreePlace(2 * node + 1, mid + 1, right, value - emptySeats, sgmTree);
        }
    }
}

void setTakenPlace(int node, int left, int right, int pos, int *sgmTree) {
    if (left == right) {
        sgmTree[node] = 1;
    } else {
        int mid = (left + right) / 2;
        if (pos <= mid) {
            setTakenPlace(2 * node, left, mid, pos, sgmTree);
        } else {
            setTakenPlace(2 * node + 1, mid + 1, right, pos, sgmTree);
        }

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

int main() {

    FILE *f, *g;
    f = fopen("schi.in", "r");
    g = fopen("schi.out", "w");

    int n, m;
    fscanf(f, "%d", &n);

    int *arr = (int*) malloc((n + 1) * sizeof(int));

    int i;

    for (i = 1; i <= n; ++i) {
        fscanf(f, "%d", &arr[i]);
    }

    int *sgmTree = (int*) calloc(4 * (n + 1), sizeof(int));  /// sgmTree [ a, b] = number of taken places , 1 = taken 0 = free
    int *finalPlace = (int*) malloc((n + 1) * sizeof(int));

    for ( i = n; i >= 1; --i) {
        int currentPlace = arr[i];
        int currentFreePlace = getFreePlace(1, 1, n, currentPlace, sgmTree );
        setTakenPlace(1, 1, n, currentFreePlace, sgmTree);
        finalPlace[currentFreePlace] = i;

    }

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

    /*

    for (i = 0; i < m; ++i) {
        int type, a, b;
        fscanf(f, "%d %d %d", &type, &a, &b);
        if (type == 1) {
            a --;
            b --;
            fprintf(g, "%d\n", getSum(1, 0, n - 1, a, b, sgmTree));

        } else {
            a --;
            int diff = arr[a] - b;
            setValue(1, 0, n - 1, a, diff, arr, sgmTree);
        }
    }

    */


    return 0;
}