Pagini recente » Cod sursa (job #2926380) | Cod sursa (job #2780639) | Cod sursa (job #1932199) | Cod sursa (job #1955062) | Cod sursa (job #568288)
Cod sursa(job #568288)
#include<fstream>
#include<iostream>
using namespace std;
const int NMAX=100005;
int aib[NMAX],used[NMAX];
inline 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 long long int& n, long long int& inv, const int& ramas)
{
int left=1,right=n,mij,sol=1;
long long int inversari;
long long int sum=(long long int) ramas*(ramas-1);
sum/=2;
inversari=inv;
if(inversari<sum)
inversari=0;
else
inversari-=sum;
while(left<=right)
{
mij=left+(right-left)/2;
int indice=query(mij,n);
if(indice>inversari+1)
right=mij-1;
else if(indice<inversari+1)
left=mij+1;
else
{
if(!used[mij])
{
sol=mij;
break;
}
else
right=mij-1;
}
}
update(sol,-1,n);
inv-=inversari;
return sol;
}
int main()
{
long long 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);
used[rez]=1;
out<<rez<<" ";
}
for(int i=1;i<=n;i++)
if(!used[i])
{
out<<i;
break;
}
out<<endl;
in.close();
out.close();
}