Cod sursa(job #2647054)

Utilizator alexradu04Radu Alexandru alexradu04 Data 2 septembrie 2020 20:05:00
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
#define mx 150010

using namespace std;

int n, gs;
int ai[mx];

void update_ai(int nod, int p, int u, int key, int ct)
{
    if (p == u)
    {
        ai[nod] = ct;
        return;
    }
    int m = (p + u) / 2;
    if (key <= m)
        update_ai(2 * nod, p, m, key, ct);
    else update_ai(2 * nod + 1, m + 1, u, key, ct);
    ai[nod] = ai[nod * 2] + ai[nod * 2 + 1];
}

int query_ai(int nod, int p, int u, int key)
{
    if (p == u)
        return p;
    int m = (p + u) / 2;
    if (ai[nod * 2] >= key)
        query_ai(nod * 2, p, m, key);
    else query_ai(nod * 2 + 1, m + 1, u, key - ai[nod * 2]);
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%ld", &n);
    for (int i = 1; i <= n; update_ai(1, 1, n, i, 1), i++);
    for (int i = 1, et = 1; i <= n; printf("%ld ", gs), i++)
    {
        et = (et + i - 1) % ai[1] + 1;
        gs = query_ai(1, 1, n, et);
        update_ai(1, 1, n, gs, 0);
        et--;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}