Cod sursa(job #381192)

Utilizator vladiiIonescu Vlad vladii Data 9 ianuarie 2010 16:24:00
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
using namespace std;

int poz, x, Arb[65600];

void update(int nod, int left, int right, int x){
    if (left==right) {
         Arb[nod]=x;
         return;
    }
    
    int mij=(left+right)>>1;
    if (poz<=mij) { update(2*nod, left, mij, x); }
    else { update(2*nod+1, mij+1, right, x); }
    
    Arb[nod]=Arb[2*nod]+Arb[2*nod+1];
}

void query(int nod, int left, int right, int x){
    if (left==right) {
         poz=left;
         return;
    }
    
    int mij=(left+right)>>1;
    if (Arb[nod*2]<x){
         x-=Arb[2*nod]; 
         query(2*nod+1, mij+1, right, x);
    }
    else query(2*nod, left, mij, x);
}

int main(){
    FILE *f1=fopen("schi.in", "r"), *f2=fopen("schi.out", "w");
    int n,i,a[30005],loc[30005];
    fscanf(f1, "%d", &n);
    for(i=1; i<=n; i++) {
         fscanf(f1, "%d", &a[i]);
    }
    for(i=1; i<=n; i++) {
         x=1; poz=i;
         update(1, 1, n, 1);
    }
    for (i=n;i>0;--i){
         query(1, 1, n, a[i]);
         loc[poz]=i;
         update(1, 1, n, 0);
    }
    for (i=1; i<=n; i++) { fprintf(f2, "%d\n", loc[i]); }
    fclose(f1); fclose(f2);
    return 0;
}