Cod sursa(job #2394340)

Utilizator victorv88Veltan Victor victorv88 Data 1 aprilie 2019 16:04:31
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int n, ramasi[30005], poz_acutala=1, distanta=1, teoretic, auxn;

void adaugare(int ind, int val)
{
    while (ind<=n) {
        ramasi[ind] += val;
        ind = ind + (ind & (-ind));
    }
}

int cautare(int ind){
    int s=0;
    while (ind)
    {
        s+=ramasi[ind];
        ind=ind-(ind&(-ind));
    }
    return s;
}

int cautare_ramasi(int val)
{
    int st=1, dr=n;
    while (st<dr)
    {
        int mij=(st+dr)/2;
        int v=cautare(mij);
        if (val<=v)
        {
            dr=mij;
        } else
            st=mij+1;
    }
    return st;
}

void stergere(int ind)
{
    while (ind)
    {
        ramasi[ind]--;
        ind=ind-(ind&(-ind));
    }
}



int main() {
    f >> n;
    for (int i=1; i<=n; ++i)
    {
        adaugare(i,1);
    }
    auxn=n;
    for (int i=1; i<=n; ++i)
    {
        teoretic=cautare(poz_acutala)+i;
        teoretic%=auxn;
        if (!teoretic)
            teoretic=auxn;
        int val=cautare_ramasi(teoretic);
        adaugare(val,-1);
        g << val << ' ';
        poz_acutala=val;
        auxn--;
    }
    return 0;
}