Cod sursa(job #3208045)

Utilizator DajaMihaiDaja Mihai DajaMihai Data 27 februarie 2024 16:15:48
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

const string fileName = "schi";

ifstream in (fileName + ".in");
ofstream out (fileName + ".out");

int n;
int aib[2 * 30000 + 1];
int v[30000];
int ans[30000];

/** Ideea: aib pentru suma totala
 *  nup
 *  Ideea: aib cu cautare binara
 *
 *
 */

int lPoz(int poz){
    return poz * 2;
}

int rPoz(int poz){
    return poz * 2 + 1;
}

void update(int poz, int val){
    int l, r, nr = 1; ///nr = pozitia in aib, poz = pozitia in v
    l = 1; r = n;
    int mid = (r + l) / 2;
    while(l <= r && l != r){
        mid = (r + l) / 2;
        if(mid < poz){
            nr = rPoz(nr);
            l = mid + 1;

        }
        else{
            r = mid;
            nr = lPoz(nr);
        }
    }
    aib[nr] = val;
    while(nr){
        aib[nr / 2] = aib[lPoz(nr / 2)] + aib[rPoz(nr / 2)];
        nr /= 2;
    }
}

int query(int nr){
    int l, r, poz;
    poz = 1; ///incepem cu varful aib-ului
    l = 1; r = n;
    int mij = (l + r) / 2;
    while(l < r){
        mij = (l + r) / 2;
        if(aib[lPoz(poz)] < nr){
            nr -= aib[lPoz(poz)];
            poz = rPoz(poz);
            l = mij + 1;
        }
        else{
            poz = lPoz(poz);
            r = mij;
        }
    }
    return l;
}

int main()
{
    in >> n;
    for(int i = 1; i <= n; i ++){
        in >> v[i];
        update(i, 1);
    }


    for(int i = n; i >= 1; i --){
        ans[query(v[i])] = i;
        update(query(v[i]), 0);
    }

    for(int i = 1; i <= n; i ++){
        out << ans[i] << endl;
    }
    return 0;
}