Cod sursa(job #3249018)

Utilizator CaldareaCiprianCaldarea Ciprian CaldareaCiprian Data 14 octombrie 2024 13:49:55
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
#include <vector>


using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");
using VI = vector<int>;
int n;
int ma;
VI aib;

int Query(int poz)
{
    int result = 0;
    for (int i = poz; i > 0; i -= (i & -i))
        result += aib[i];

    return result;
}

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

int Cb(int nr)
{
    int i = ma;
    int poz = 0;
    int lastgood = 0;
    for (; i > 0; i >>= 1)
    {
        if (poz + i > n)
            continue;

        poz += i;
        if (Query(poz) >= nr)
        {
            lastgood = poz;
            poz -= i;
        }
    }

    return lastgood;
}


int main()
{
    fin >> n;
    aib = VI(n + 1);
    for (int i = 1; i <= n; ++i)
        Update(i, 1);

    fout << 2 << ' ';
    Update(2, -1);
    int cur = 2;
    int nr;
    for (ma = 1; ma <= n; ma <<= 1);

    ma >>= 1;
    for (int i = 1; i < n; ++i)
    {
        nr = Query(n);
        cur = (cur  + i - 1) % nr + 1;
        int poz = Cb(cur);
        fout << poz << ' ';
        Update(poz, -1);

    }

}