Cod sursa(job #3267188)

Utilizator cristian46290Petre Cristian cristian46290 Data 11 ianuarie 2025 10:15:29
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int nMax = 3e4 + 5;

int n;
int a[nMax], aib[nMax], rezV[nMax];

void update(int x,int val)
{
    for (int i = x;i <= n;i+=i&-i)aib[i] += val;
}

int sum(int x)
{
    int rez = 0;
    for (int i = x;i >= 1;i-=i&-i)rez += aib[i];
    return rez;
}

int cb(int s)
{
    int st = 1,dr = n;
    int rez = nMax;
    int mij;
    while(st <= dr){
        mij = (st + dr) / 2;
        if (sum(mij) > s)dr = mij - 1;
        else if (sum(mij) < s)st = mij + 1;
        else{
            rez = min(mij,rez);
            dr = mij - 1;
        }
    }
    return rez;
}

int main()
{
    f >> n;
    for (int i = 1;i <= n;i++){
        f >> a[i];
        update(i,1);
    }
    for (int i = 1;i <= n;i++){
        int j = i;
        while(j > sum(n))j -= sum(n);
        rezV[i] = (cb(j) + 1) % n;
        if (rezV[i] == 0)rezV[i] = n;
        update(cb(j),-1);
    }
    for (int i = 1;i <= n;i++)g << rezV[i] << " ";
}