Cod sursa(job #2664385)

Utilizator Iulia14iulia slanina Iulia14 Data 28 octombrie 2020 16:13:13
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>

using namespace std;
ifstream cin ("order.in");
ofstream cout ("order.out");
int seg[120005];
void update(int nod, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        seg[nod] = val;
        return;
    }
    int mid = (st + dr) / 2;
    if (poz <= mid)
        update(2 * nod, st, mid, poz, val);
    else
        update(2 * nod + 1, mid + 1, dr, poz, val);
    seg[nod] = seg[2 * nod] + seg[2 * nod + 1];
}
int query(int nod, int st, int dr, int cnt)
{
    if (st == dr)
        return st;
    int mid = (st + dr) / 2;
    if (seg[nod * 2] < cnt)
        return query(nod * 2 + 1, mid + 1, dr, cnt - seg[nod * 2]);
    else
        return query(nod * 2, st, mid, cnt);

}
int main()
{
    int n, i, x = 1;
    cin >> n;
    for (i = 1; i <= n; i++)
        update(1, 1, n, i, 1);
    for (i = 1; i <= n; i++)
    {
        x = (x + i - 1) % (n - i + 1);
        int y = query(1, 1, n, x + 1);
        cout << y << " ";
        update(1, 1, n, y, 0);
    }
    return 0;
}