Cod sursa(job #2777118)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 22 septembrie 2021 10:10:19
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

long int n;
long long bit[100010];

void update (int i, int val)
{
    while (i <= n)
    {
        bit[i] += val;
        i += (i & -i);
    }
}
long long ps(int i)
{
    int sum = 0;
    while (i > 0)
    {
        sum += bit[i];
        i -= (i & -i);
    }
    return sum;
}

int cb (int x)
{
    int h = n, l = 1;int sol = n;
    while (h >= l)
    {
        int m = (l + h) / 2;
        int pos = ps(m);
        if (pos <= x)
        {
            sol = m;
            l = m + 1;
        }
        else {
            h = m - 1;
        }
    }
    return sol;
}

int main ()
{
    in >> n;
    int poz = 2;
    for (int i = 1; i <= n; i ++)
    {
        update (i, 1);
    }
    /*while (n - elim)
    {
        poz = elim % (n - elim);
        if (poz == 0)
            poz = n - elim;
        cout << poz << " ? " << elim << " ";
        int newElim = bs(poz);
        cout << newElim << " : ";
        update (newElim, -1);
        for (int i = 1; i <= n; i++)
        {
            cout << ps(i) << " ";
        }
        cout << "\n";
        
        elim ++;
    }*/

    for (int i = 1; i <= n; i++)
    {
        poz = (poz + i - 1) % (n - i + 1);
        if (poz == 0)
        {
            poz = n - i + 1;
        }
        int sol = cb(poz);
        while (ps(sol) == poz)
            sol --;
        sol ++;
      //  cout << "i = " << i << " ";
        out << sol << " ";
        update (sol, -1);
    }
}