Pagini recente » Cod sursa (job #341412) | Cod sursa (job #825278) | Cod sursa (job #2896406) | Cod sursa (job #3265151) | Cod sursa (job #795104)
Cod sursa(job #795104)
#include<iostream>
#include<fstream>
using namespace std;
const int NMAX = 100001;
int v[NMAX],arb[4*NMAX],poz,val,uval;
inline long long perm(int n)
{
return (1LL*n*(n-1))/2;
}
void update(int nod, int st, int dr)
{
int mij;
if(st==dr) {
arb[nod]=uval;
return ;
}
mij=(st+dr)/2;
if(poz<=mij)
update(2*nod,st,mij);
else update(2*nod+1,mij+1,dr);
arb[nod]=arb[2*nod]+arb[2*nod+1];
}
void query(int nod, int st, int dr)
{
int mij;
if(st==dr) {
val=st;
return ;
}
mij=(st+dr)/2;
if(poz<=arb[2*nod])
query(2*nod,st,mij);
else {
poz=poz-arb[2*nod];
query(2*nod+1,mij+1,dr);
}
}
int main ()
{
int n,i;
long long k,p;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
f>>n>>k;
f.close();
uval=1;
for(i=1;i<=n;i++) {
poz=i;
update(1,1,n);
}
uval=0;
for(i=1;i<=n;i++) {
p=perm(n-i);
if(p==k)
break;
else if(p>k) {
poz=1;
query(1,1,n);
g<<val<<" ";
v[val]=1;
poz=val;
update(1,1,n);
}
else {
poz=0LL+k-p+1;
k=0LL+k-poz+1;
query(1,1,n);
g<<val<<" ";
v[val]=1;
poz=val;
update(1,1,n);
}
}
for(i=n;i>=1;i--)
if(v[i]==0)
g<<i<<" ";
g<<'\n';
g.close();
return 0;
}