Pagini recente » Cod sursa (job #2645836) | Cod sursa (job #779250) | Cod sursa (job #1659918) | Cod sursa (job #2122775) | Cod sursa (job #2753171)
#include <fstream>
using namespace std;
const int N = 3e4 + 1;
const int L = 14;
int v[N], aib[N], cf[N], n;
void actualizare(int p, int val)
{
while (p <= n)
{
aib[p] += val;
p += (p & (-p));
}
}
int caut(int val)
{
if (val == 0)
{
return -1;
}
int r = 0, pas = 1 << L;
while (pas != 0)
{
if (r + pas <= n && aib[r + pas] < val)///caut cel mai lung prefix cu suma < val
{
val -= aib[r + pas];
r += pas;
}
pas >>= 1;
}
r++;///1+lungimea celui mai lung cu suma < val = cel mai scurt cu suma >= val
return r;
}
int main()
{
ifstream in("schi.in");
ofstream out("schi.out");
in >> n;
///suma obtinuta de aib pana la poz i = cate locuri libere au ramas pana la poz i
for (int i = 1; i <= n; i++)
{
in >> v[i];
actualizare(i, 1);///fiecare loc de la 1 la n e initial liber
}
in.close();
for (int i = n; i >= 1; i--)
{
///determin pozitia in clasamanetul final a celui care a concurat al i-lea
int poz = caut(v[i]);///cel mai scurt prefix cu suma (locurilor libere) = v[i]
actualizare(poz, -1);///am un loc liber mai putin pentru interogarile de la poz in sus
cf[poz] = i;
}
for (int i = 1; i <= n; i++)
{
out << cf[i] << "\n";
}
out.close();
return 0;
}