Pagini recente » Cod sursa (job #47653) | Cod sursa (job #3031958) | Cod sursa (job #278369) | Cod sursa (job #2503807) | Cod sursa (job #2833407)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int N;
vector<int> a;
vector<int> aib;
vector<int> res;
// x[pos] += val
void update(int pos, int val);
// calculeaza suma x[1] + x[2] + ... + x[n]
int query(int x);
void ReadData();
void Solve();
int Search(int pos); // cauta a pos-a pozitie libera
int main()
{
ReadData();
Solve();
fin.close();
fout.close();
return 0;
}
void ReadData()
{
fin >> N;
res = a = aib = vector<int>(N + 1);
for (int i = 1; i <= N; ++i)
{
fin >> a[i];
update(i, 1);
}
}
void Solve()
{
for (int i = N; i >= 1; --i)
{
int pos = Search(a[i]);
res[pos] = i;
update(pos, -1);
}
for (int i = 1; i <= N; ++i)
fout << res[i] << '\n';
}
int Search(int pos)
{
int l{1}, r{N}, mid, ans;
while (l <= r)
{
mid = (l + r) / 2;
int q = query(mid);
if (q >= pos)
{
r = mid - 1;
if (q == pos)
ans = mid;
}
else
l = mid + 1;
}
return ans;
}
void update(int pos, int val)
{
for (int i = pos; i <= N; i += i & (-i))
aib[i] += val;
}
int query(int x)
{
int res = 0;
for (int i = x; i > 0; i -= i & (-i))
res += aib[i];
return res;
}