Pagini recente » Cod sursa (job #2944518) | Cod sursa (job #1561930) | Cod sursa (job #1229189) | Cod sursa (job #1025914) | Cod sursa (job #2876989)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("schi.in");
ofstream g ("schi.out");
int n, x;
vector <int> v, bxPerm, bxTree;
void update(int x, int val)
{
while (x <= n)
{
bxTree[x] += val;
x += (x&-x);
}
}
int query(int x)
{
int sol = 0;
while (x)
{
sol += bxTree[x];
x -= (x&-x);
}
return sol;
}
int bs_perm(int val)
{
int st = 1, dr = n, mij, x = -1, sol, aux;
while (st <= dr)
{
mij = (st + dr) / 2;
aux = query(mij);
if (aux == val)
{
sol = mij;
dr = mij - 1;
}
else if (aux < val) st = mij + 1;
else dr = mij - 1;
}
return sol;
}
vector <int> solve(vector <int> v)
{
for (int i = 0; i < n; ++i)
update(i + 1, 1);
for (int i = n - 1; i >= 0; --i)
{
x = bs_perm(v[i]);
bxPerm[x] = i + 1;
update(x, -1);
}
for (int i = 1; i <= n; ++i) g << bxPerm[i] << '\n';
}
int main()
{
f >> n;
int xInp;
for (int i = 0; i < n; ++i)
{
f >> xInp;
v.push_back(xInp);
}
bxPerm.resize(v.size() + 1);
fill(bxPerm.begin(), bxPerm.end(), 0);
bxTree.resize(v.size() + 1);
fill(bxTree.begin(), bxTree.end(), 0);
solve(v);
return 0;
}