Pagini recente » Cod sursa (job #469140) | Cod sursa (job #2929972) | Cod sursa (job #2324609) | Cod sursa (job #2916512) | Cod sursa (job #3155049)
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin ("schi.in");
ofstream fout ("schi.out");
const int NMAX = 30000;
bool fr[NMAX + 5];
int n, v[NMAX + 5], ans[NMAX + 5];
vector <int> aint;
int rmax;
void getSizes()
{
int nodes = 0, exp = log2(n);
if((1 << exp) != n)
exp++;
nodes = 2 * (1 << exp) - 1;
rmax = 1 << exp;
aint.resize(nodes + 5);
}
void build(int node = 1, int left = 1, int right = rmax)
{
if(left == right and left > n)
{
aint[node] = 0;
return;
}
if(left == right)
{
aint[node] = 0;
return;
}
int mid = (left + right) / 2;
build(2 * node, left, mid);
build(2 * node + 1, mid + 1, right);
aint[node] = aint[2 * node] + aint[2 * node + 1];
}
void update(int pos, int node = 1, int left = 1, int right = rmax)
{
if(left == right and left > n)
{
aint[node] = 0;
return;
}
if(left == right)
{
aint[node] = 1;
return;
}
int mid = (left + right) / 2;
if(pos <= mid)
update(pos, 2 * node, left, mid);
if(mid < pos)
update(pos, 2 * node + 1, mid + 1, right);
aint[node] = aint[2 * node] + aint[2 * node + 1];
}
int query(int leftq, int rightq, int node = 1, int left = 1, int right = rmax)
{
if(leftq <= left and right <= rightq)
return aint[node];
int mid = (left + right) / 2, leftans = 0, rightans = 0;
if(leftq <= mid)
leftans = query(leftq, rightq, 2 * node, left, mid);
if(mid < rightq)
rightans = query(leftq, rightq, 2 * node + 1, mid + 1, right);
return leftans + rightans;
}
int BinarySearch(int pos)
{
int left = 1, right = n;
while(left <= right)
{
int mid = (left + right) / 2;
int q = query(1, mid);
if(mid - q == pos and fr[mid] == 0)
return mid;
if(mid - q == pos and fr[mid] == 1)
right = mid - 1;
else if(mid - q < pos)
left = mid + 1;
else right = mid - 1;
}
}
int main()
{
fin >> n;
getSizes();
for(int i = 1; i <= n; i++)
fin >> v[i];
build();
for(int i = n; i >= 1; i--)
{
int pos = BinarySearch(v[i]);
ans[pos] = i;
fr[pos] = 1;
update(pos);
}
for(int i = 1; i <= n; i++)
fout << ans[i] << '\n';
fin.close();
fout.close();
return 0;
}