Cod sursa(job #1488249)

Utilizator tudormaximTudor Maxim tudormaxim Data 18 septembrie 2015 11:30:02
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 3e4 + 5;
int n, aib[nmax], viz[nmax], pmax=1;

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

int query(int nr)
{
    int sol = 0;
    for(int p=pmax; p && nr; p=p>>1)
        if(sol+p<=n && aib[sol+p]<=nr)
        {
            nr-=aib[sol + p];
            sol+=p;
        }
    while (viz[sol]) sol--;
    return sol;
}

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    int i, x, ind, mod;
    scanf("%d", &n);
    while (pmax<<1 <= n) pmax=pmax<<1;
    for(i=1; i<=n; i++)  update(i, 1);

    for(x=2, i=1; i<=n; i++)
    {
        mod=n-i+1;
        x=(x+n-mod)%mod;
        if(!x) x=mod;
        ind=
        query(x);
        update(ind, -1);
        viz[ind] = 1;
        printf("%d ", ind);
    }
    return 0;
}
///mess
/*#include <bits/stdc++.h>
using namespace std;
const int nmax = 100005;

struct arbore
{
    vector <int> v;
    int on=1, nr;
} arb[3*nmax];

void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)
    {
        arb[nod].v.push_back(val);
        if(arb[nod].on==1) arb[nod].on=0;
        else arb[nod].on=1;
        return;
    }
    int m=(st+dr)>>1;
    if(poz<=m) update(nod<<1, st, m, poz, val);
    else update(nod<<1|1, m+1, dr, poz, val);
    arb[nod].on=arb[nod<<1].on+arb[nod<<1|1].on;
    arb[nod].v.push_back()
}

void query(int nod, int st, int dr, int start, int finish)
{
    if(start<=st && dr<=finish)
    {
        if(on[nod])
        return;
    }
    int m=(st=dr)>>1;
    if(start<=m) query(nod<<1, st, m, start, finish);
    if(m<finish) query(nod<<1|1, m+1, dr, start, finsih);

}

int main()
{
    freopen("mess.in", "r", stdin);
    freopen("mess.out", "w", stdout);
    int n, m, i, x, p, q, k, v[nmax];
    scanf("%d %d", &n, &m);
    while(dim<=n) dim=dim<<1;
    for(i=1; i<=n; i++)
    {
        scanf("%d", &v[i]);
        update(1, 1, n, i, v[i]);
    }

    while(m--)
    {
        scanf("%d %d", &x, &p);
        if(x==1) update(1, 1, n, i, v[i]);
        else
        {

            scanf("%d %d", &q, &k);
            query(1, 1, n, p, q);
        }
    }

    return 0;
}*/