Cod sursa(job #742672)

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

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

const int N=400005;

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

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

void update(int poz,int st,int dr,int x,int 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(int poz,int st,int dr,int 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);
    }

}

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



int main()
{
	int 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-(long long)(n-i)*(n-i-1)/2+1);
			k-=(k-(long long)(n-i)*(n-i-1)/2);
            out<<q<<" ";
			update(1,1,n,q,0);
		}
    }

    out<<"\n";

    return 0;
}