Pagini recente » Cod sursa (job #3145782) | Cod sursa (job #139127) | Cod sursa (job #399473) | Cod sursa (job #1670505) | Cod sursa (job #2146497)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
const int NMax=15005;
class SegmentTree
{
public:SegmentTree(int size)
{
N=size;
int lg=ceil(log2(N));
ST.resize(1<<lg+1);
}
public:void Insert(int index)
{
Insert(index,1,1,N);
}
public:void Query(int index)
{
Query(1,index,1,N);
}
private:int N;
private:vector<int> ST;
private:void Insert(int index,int node,int left,int right)
{
if(left==right)
{
ST[node]=1;
return;
}
int middle=(left+right)/2;
Insert(index,2*node,left,middle);
Insert(index,2*node+1,middle+1,right);
ST[node]+=ST[2*node]+ST[2*node+1];
}
private:void Query(int node,int index,int left, int right)
{
if(left==right)
{
ST[node]=0;
fout<<left<<" ";
return;
}
int middle=(left+right)/2;
if(index<=ST[2*node])
Query(2*node,index,left,middle);
else
Query(2*node+1,index-ST[2*node],middle+1,right);
ST[node]=ST[2*node]+ST[2*node+1];
}
};
int N,K;
int main()
{
fin>>N>>K;
SegmentTree segmentTree(N);
segmentTree.Insert(1);
for(int i=N-1;i>=0;i--)
if(K<=i*(i-1)/2)
segmentTree.Query(1);
else
segmentTree.Query(K-i*(i-1)/2+1), K=i*(i-1)/2;
return 0;
}