Cod sursa(job #2625362)

Utilizator anacomoAna-Maria Comorasu anacomo Data 5 iunie 2020 21:53:59
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
using namespace std;

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

int v[100000], n;
void update(int poz, int x)
{
    for (int i = poz; i <= n; i += (i & -i))
        v[i] += x;
}
int cautare(int poz)
{
    int i = 0;
    for (int p = 1 << 15; p; p >>= 1)
        if (i + p <= n && v[i + p] < poz)
        {
            poz -= v[i + p];
            i += p;
        }
    return i + 1;
}
int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        update(i, 1);

    int k = 1, nr = n;
    for (int i = 1; i <= n; ++i)
    {
        k += i;
        k %= nr;
        if (k == 0)
            k = nr;

        int aux = cautare(k);
        update(aux, -1);
        nr -= 1;
        k -= 1;
        fout << aux << " ";
    }
    return 0;
}