Pagini recente » Cod sursa (job #2458128) | Cod sursa (job #2033680) | Cod sursa (job #1628170) | Cod sursa (job #2239836) | Cod sursa (job #2442844)
#include <fstream>
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
const int NMAX = 1e5 + 5;
int N, A[NMAX], AIB[NMAX];
long long K;
static inline int UB (int X)
{
return (X & (-X));
}
static inline void Update (int pos, int val)
{
for(int i = pos; i <= N; i += UB(i))
AIB[i] += val;
}
static inline int Query (int pos)
{
int sum = 0;
for(int i = pos; i >= 1; i -= UB(i))
sum += AIB[i];
return sum;
}
static inline long long Maxim_Inv (int Left, int Right)
{
int Lg = (Right - Left + 1);
return 1LL * (1LL * Lg * 1LL * (Lg - 1)) / (1LL * 2);
}
static inline int CB (int X)
{
int Left = 1, Right = N, pos = 0;
while(Left <= Right)
{
int Mid = (Left + Right) / 2;
if(Query(Mid) >= X)
{
pos = Mid;
Right = Mid - 1;
}
else
Left = Mid + 1;
}
return pos;
}
int main()
{
f.tie(NULL);
f >> N >> K;
for(int i = 1; i <= N; ++i)
Update(i, 1);
for(int i = 1; i <= N; ++i)
{
long long Max = Maxim_Inv(i + 1, N);
if(K <= Max)
A[i] = CB(1);
else
{
int Diff = (int)(K - Max);
A[i] = CB(Diff + 1);
K -= 1LL * Diff;
}
Update(A[i], -1);
}
for(int i = 1; i <= N; ++i)
g << A[i] << ' ';
g << '\n';
return 0;
}