Pagini recente » Cod sursa (job #266703) | Cod sursa (job #885947) | Cod sursa (job #380692) | Cod sursa (job #458289) | Cod sursa (job #2614567)
#include <fstream>
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
using ll = long long;
const int NMAX = 1e5 + 5;
int N;
ll K;
int A[NMAX];
class FenwickTree
{
int A[NMAX];
private:
inline int UB (int X)
{
return (X & (-X));
}
inline int Query (int pos)
{
int r = 0;
for(int i = pos; i >= 1; i -= UB(i))
r += A[i];
return r;
}
public:
inline void Update (int pos, int Val)
{
for(int i = pos; i <= N; i += UB(i))
A[i] += Val;
return;
}
inline int Find_the_n_th_Active (int n)
{
int Left = 1, Right = N, ans = N;
while(Left <= Right)
{
int Mid = (Left + Right) >> 1;
if(Query(Mid) >= n)
{
ans = Mid;
Right = Mid - 1;
}
else
Left = Mid + 1;
}
return ans;
}
} AIB;
static inline void Read ()
{
f.tie(nullptr);
f >> N >> K;
return;
}
static inline void Initialize (int N)
{
for(int i = 1; i <= N; ++i)
AIB.Update(i, 1);
return;
}
static inline ll Count (int Left, int Right)
{
int Lg = (Right - Left + 1);
return (1LL * (1LL * Lg * (1LL * Lg - 1LL)) >> 1LL);
}
static inline void Solve ()
{
Initialize(N);
for(int i = 1; i <= N; ++i)
{
ll Maximum_Remaining = Count(i + 1, N);
int Id = 1;
if(Maximum_Remaining < K)
{
int Delta = K - Maximum_Remaining;
Id = Delta + 1;
K -= 1LL * Delta;
}
A[i] = AIB.Find_the_n_th_Active(Id);
AIB.Update(A[i], -1);
}
return;
}
static inline void Write ()
{
for(int i = 1; i <= N; ++i)
{
g << A[i];
if(i != N)
g << ' ';
}
g << '\n';
return;
}
int main()
{
Read();
Solve();
Write();
return 0;
}