Cod sursa(job #3004486)

Utilizator Vincent47David Malutan Vincent47 Data 16 martie 2023 12:54:23
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <climits>

using namespace std;
ifstream cin("order.in");
ofstream cout("order.out");

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

int query(int p)
{
    int s = 0;
    for(int i = p; i; i -= i & -i)
        s += aib[i];
    return s;
}

int cb(int x)
{
    int s = 1, d = n, mi = INT_MAX, r;

    while(s <= d)
    {
        int m = (s + d) >> 1;
        r = query(m);
        if (r == x){
            mi = min(mi, m);
            d = m - 1;
        }

        else if (r > x)
            d = m - 1;
        else s = m + 1;
    }
    return mi;
}


int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
        update (i, 1);

    int summ = 1, nrm = n, p, x, y;
    for (int i = 1; i < n; i++)
    {
        y = i % nrm;

        if (i > 1)
			summ = query (p);

        x = y + summ;
        x %= nrm;

        if (!x) x = nrm;
        p = cb (x);
        cout << p << ' ';
        update (p, -1);
        nrm--;
    }

    p = cb (1);
    cout << p;


    return 0;
}