Mai intai trebuie sa te autentifici.
Cod sursa(job #1825814)
Utilizator | Data | 9 decembrie 2016 18:22:41 | |
---|---|---|---|
Problema | Farfurii | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.39 kb |
#include <fstream>
#include <algorithm>
int n, k;
int tree[400004];
void modify(int node, int left, int right, int position, int value)
{
if (left==right)
{
tree[node] = value;
return;
}
int middle = (left+right)>>1;
if (position <= middle)
modify(node<<1, left, middle, position, value);
else
modify(node<<1|1, middle+1, right, position, value);
tree[node] = tree[node<<1] + tree[node<<1|1];
}
int query(int node, int left, int right, int value)
{
if (left==right) return left;
int middle = (left+right)>>1;
if (value <= tree[node<<1])
return query(node<<1, left, middle, value);
else
return query(node<<1|1, middle+1, right, value-tree[node<<1]);
}
int main()
{
std::ifstream fin("farfurii.in");
std::ofstream fout("farfurii.out");
fin>>n>>k;
for (int i = 1; i <= n; ++i)
modify(1, 1, n, i, 1);
for (int i = n; i > 0; --i)
{
int needed_inversions = std::max(0, k-(i-1)*(i-2)/2);
k-=needed_inversions;
int place = query(1, 1, n, needed_inversions+1);
fout<<place<<" ";
modify(1, 1, n, place, 0);
}
fin.close();
fout.close();
return 0;
}