Cod sursa(job #742673)

Utilizator ioanabIoana Bica ioanab Data 30 aprilie 2012 23:59:25
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
using namespace std;

ifstream in("farfurii.in");
ofstream out("farfurii.out");

const int N=400005;

long long aint[N];
long long n,rez;
long long k;

inline int max(int a,int b)
{
    return a>b ? a : b ;
}

void update(long long poz,long long st,long long dr,long long x,long long val)
{
    if(st==dr)
    {
        aint[poz]=val;
        return;
    }

    int m=(st+dr)/2,S=poz*2,D=S+1;

    if(x<=m)
        update(S,st,m,x,val);
    else
        update(D,m+1,dr,x,val);

    aint[poz]=aint[S]+aint[D];
}

void query(long long poz,long long st,long long dr,long long val)
{
    if(st==dr)
	{
        rez=st;
		return;
	}

    int m=(st+dr)/2, S=poz*2, D=S+1;

    if(aint[S]>=val)
        query(S,st,m,val);
    else
    {
        val-=aint[S];
        query(D,m+1,dr,val);
    }

}

long long query(long long val)
{
	rez=0;
	query(1,1,n,val);
	return rez;
}



int main()
{
	long long i,q;
	in>>n>>k;   
	
    for(i=1;i<=n;i++)
        update(1,1,n,i,1);

    for(i=1;i<=n;i++)
    {
        if(k <=(n-i)*(n-i-1)/2)
		{
            q=query(1);
			out<<q<<" ";
			update(1,1,n,q,0);
		}

        else
		{
			q=query(k-(n-i)*(n-i-1)/2+1);
			k-=(k-(n-i)*(n-i-1)/2);
            out<<q<<" ";
			update(1,1,n,q,0);
		}
    }

    out<<"\n";

    return 0;
}