Pagini recente » Cod sursa (job #1840077) | Cod sursa (job #687446) | Cod sursa (job #1140062) | Cod sursa (job #2745260) | Cod sursa (job #568271)
Cod sursa(job #568271)
#include<fstream>
#include<iostream>
using namespace std;
const int NMAX=100005;
int aib[NMAX],used[NMAX];
int lsb(int x)
{
return x&(-x);
}
void update(int poz, int val, int n)
{
while(poz<=n)
{
aib[poz]+=val;
poz+=lsb(poz);
}
}
int query(int poz, int n)
{
int sum=0;
while(poz>0)
{
sum+=aib[poz];
poz-=lsb(poz);
}
return sum;
}
int search(const int& n, int& inv, const int& ramas)
{
int left=1,right=n,mij,sol,inversari;
int sum=ramas*(ramas-1);
sum/=2;
inversari=inv;
if(inversari<sum)
inversari=0;
else
inversari-=sum;
while(left<=right)
{
mij=left+(right-left)/2;
if(query(mij,n)>inversari+1)
right=mij-1;
else if(query(mij,n)<inversari+1)
left=mij+1;
else
{
if(!used[mij])
{
sol=mij;
break;
}
else
right=left-1;
}
}
update(sol,-1,n);
inv-=inversari;
return sol;
}
int main()
{
int n,k;
ifstream in("farfurii.in");
ofstream out("farfurii.out");
in>>n>>k;
for(int i=1;i<=n;i++)
update(i,1,n);
for(int i=1;i<=n-1;i++)
{
int rez=search(n,k,n-i);
out<<rez<<" ";
used[rez]=1;
}
for(int i=1;i<=n;i++)
if(!used[i])
{
out<<i;
break;
}
out<<endl;
in.close();
out.close();
}