Pagini recente » Cod sursa (job #3123033) | Cod sursa (job #196358) | Cod sursa (job #1548815) | Cod sursa (job #2307000) | Cod sursa (job #2862947)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int n;
int arbint[100000];
int v[30005];
int ans[30005];
int LfSon(int node)
{
return node * 2;
}
int RgSon(int node)
{
return node * 2 + 1;
}
int Query(int node, int lf, int rg, int val)
{
if (lf == rg)
{
return lf;
}
int mid = (lf + rg) / 2;
if (arbint[LfSon(node)] < val)
{
return Query(RgSon(node), mid + 1, rg, val - arbint[LfSon(node)]);
}
else
{
return Query(LfSon(node), lf, mid, val);
}
}
void Update(int node, int lf, int rg, int pos, int val)
{
if (lf == rg)
{
arbint[node] = val;
return;
}
int mid = (lf + rg) / 2;
if (pos <= mid)
{
Update(LfSon(node), lf, mid, pos, val);
}
else
{
Update(RgSon(node), mid + 1, rg, pos, val);
}
arbint[node] = arbint[LfSon(node)] + arbint[RgSon(node)];
}
void Init(int node, int lf, int rg, int val)
{
if (lf == rg)
{
arbint[node] = val;
return;
}
int mid = (lf + rg) / 2;
Init(LfSon(node), lf, mid, val);
Init(RgSon(node), mid + 1, rg, val);
arbint[node] = arbint[LfSon(node)] + arbint[RgSon(node)];
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> v[i];
}
int log = log2(n);
if ((1 << log) < n)
{
log++;
}
int upperBound = 1 << log;
Init(1, 1, upperBound, 1);
for (int i = n; i > 0; i--)
{
int index = Query(1, 1, upperBound, v[i]);
cout << index << ' ';
Update(1, 1, upperBound, index, 0);
ans[index] = i;
}
for (int i = 1; i <= n; i++)
{
fout << ans[i] << '\n';
}
}