Cod sursa(job #3268121)

Utilizator octavurlurleteanu alexandru octavian octavurl Data 13 ianuarie 2025 18:14:29
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
vector<int>v, aib;
int n;
static inline void add(int x,int val)
{
    for (int i = x; i <= n; i += i & (-i))
        aib[i] += val;
}
static inline int query(int x)
{
    int suma = 0;
    for (int i = x; i >= 1; i -= i & (-i))
        suma += aib[i];
    return suma;
}
static inline int cautare_binara(int val)
{
    int st = 1, dr = n, p = -1;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        int suma = query(mij);
        if (suma >= val)
        {
            p = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return p; 
}
static inline void citire()
{
    fin >> n;
    v.resize(n + 1);
    aib.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        add(i, 1);
}
static inline void rezolvare()
{
    int m = n;
    int poz = 2;
    for (int i = 1; i <= n; ++i)
    {
        poz = (poz + i - 1) % m;
        if (poz == 0)
            poz = m;
        --m;
        int c = cautare_binara(poz);
        fout << c << ' ';
        add(c, -1);
    }
}
int main()
{
    citire();
    rezolvare();
}