Pagini recente » Cod sursa (job #1502870) | Cod sursa (job #1895202) | Cod sursa (job #2601579) | Cod sursa (job #1238617) | Cod sursa (job #3301901)
#include <fstream>
#include <vector>
#include <cassert>
#define ll long long
using namespace std;
const int NMAX = 1e5;
bool seen[NMAX + 1];
ll gauss(int val)
{
return 1LL * val * (val - 1) / 2;
}
int n;
struct aib
{
int c[NMAX + 1];
void update(int poz, int val)
{
for (; poz <= n; poz += poz & -poz)
c[poz] += val;
}
int query(int poz)
{
int ans = 0;
for (; poz; poz -= poz & -poz)
ans += c[poz];
return ans;
}
};
aib ds;
int main()
{
ifstream cin("farfurii.in");
ofstream cout("farfurii.out");
int i, j;
ll k;
cin >> n >> k;
int big;
for (big = 0; (1 << big) <= n; big++);
big--;
for (i = 1; i <= n; i++)
ds.update(i, 1);
for (i = 1; i <= n; i++)
{
ll dif = k - gauss(n - i);
//query(poz - 1) >= dif
int ax = 0;
int sum = 0;
for (j = big; j >= 0; j--)
if (ax + (1 << j) <= n and sum + ds.c[ax + (1 << j)] < dif)
{
ax += (1 << j);
sum += ds.c[ax];
}
//ax e primul mai mic, ax + 1 e primul mai mare
//te intereseaza primul 1 dupa ax + 1
if (dif <= 0)
ax = 0;
else
ax++;
int ax2 = 0;
for (j = big; j >= 0; j--)
if (ax2 + (1 << j) <= n)
{
if (ds.c[ax2 + (1 << j)] == 0 or ax2 + (1 << j) <= ax)
ax2 += (1 << j);
}
ax2++;
cout << ax2 << " ";
k -= ds.query(ax2 - 1);
ds.update(ax2, -1);
}
}