Cod sursa(job #1266899)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 19 noiembrie 2014 11:36:32
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
/*#include <cstdio>
#include <algorithm>

using namespace std;

const int nmax=100000;
int arint[4*nmax+1];
int n;

void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)arint[nod]=val;
    else
    {
        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);
        arint[nod]=arint[2*nod]+arint[2*nod+1];
    }
}

int ans;

void querry(int nod, int st, int dr, int x, int y)
{
    if(st>=x && y>=dr)
    {
        ans+=arint[nod];
        return;
    }
    int mid=(st+dr)/2;
    if(x<=mid)querry(2*nod, st, mid, x, y);
    if(y>mid)querry(2*nod+1, mid+1, dr, x, y);
}

int binary(int x, int y, int val)
{
    int st=x, dr=y;
    int last= x;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        ans=0;
        querry(1, 1, n, x, mid);
        if(ans>=val)
		{
            dr=mid-1;
            last=mid;
        }
        else if(ans<val)
			st= mid+1;
    }
    return last;
}

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        update(1, 1, n, i, 1);
    int poz=1;
    for(int i=1;i<=n;i++)
    {
        int lg=(i-1)%(n-i+1)+1;
        ans=0;
        querry(1, 1, n, poz+1, n);
        int limit= ans;
        if(lg<=limit)
            poz=binary(poz+1, n, lg);
        else poz=binary(1, poz, lg-limit);
        update(1, 1, n, poz, 0);
        printf("%d ", poz);
    }
    return 0;
}
*/
#include <cstdio>
#include <algorithm>

using namespace std;

const int nmax=100000;
int aib[nmax+1];
int n;

inline int lsb(int x)
{
	return x & -x;
}

void update(int pos, int val)
{
	for(int i=pos; i<=n; i+=lsb(i))
		aib[i]+=val;
}

int querry(int pos)
{
	int ans=0;
	for(int i=pos; i>0; i-=lsb(i))
		ans+=aib[i];
	return ans;
}

int binary(int x, int y, int val)
{
	int last;
	int ans=0, sc=0;
	int t=querry(x-1);
	for(int i=1<<17; i>0; i>>=1)
		if(ans+i<=n)
		{
			if(sc+aib[ans+i]-t<val)
			{
				ans+=i;
				sc+=aib[ans];
			}
			else if(sc+aib[ans+i]-t==val)
				last=ans+i;
		}
	return last;
}

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        update(i, 1);
    int poz=1;
    for(int i=1;i<=n;i++)
    {
        int lg=(i-1)%(n-i+1)+1;
        int limit=querry(n) - querry(poz);
        if(lg<=limit)
            poz=binary(poz+1, n, lg);
        else poz=binary(1, poz, lg-limit);
        update(poz, -1);
        printf("%d ", poz);
    }
    return 0;
}