Pagini recente » Cod sursa (job #2181573) | Cod sursa (job #538653) | Cod sursa (job #2848173) | Cod sursa (job #2946703) | Cod sursa (job #2381735)
#include <fstream>
#define MaxN 30000
#define DIM 174
using namespace std;
ifstream f ("schi.in");
ofstream g ("schi.out");
int n;
int sol[MaxN + 5];
int v[MaxN+5];
int BATON[DIM+DIM];
bool NEAT[MaxN + 5];
void scad (int poz)
{
int bucata = (poz + DIM - 1) / DIM;
BATON[bucata]--;
NEAT[poz] = 1;
}
int sume (int poz)
{
int bucata_poz = (poz + DIM - 1) / DIM;
int lim_poz = (bucata_poz - 1) * DIM+1;
int rez = 0;
for (int i = lim_poz; i <= poz; ++i)
{
rez = rez + 1 - NEAT[i];
}
for (int i = 1; i < bucata_poz; ++i)
rez = rez + BATON[i];
return rez;
}
int main()
{
f >> n;
for (int i = 1; i <= n; ++i) {
f >> v[i];
BATON[i] = DIM;
}
int bucata = (n + DIM - 1) / DIM;
BATON[bucata] = n - (bucata-1) * DIM;
for (int i = n; i > 0; --i)
{
int st = 1;
int dr = n;
int L = n + 1;
while (st <= dr)
{
int mij = (st + dr) / 2;
if (sume(mij) == v[i] && mij < L && NEAT[mij] == false)
{
L = mij;
dr = mij - 1;
}
else if (sume(mij) < v[i])
{
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
sol[L] = i;
scad(L);
}
for (int i = 1; i <= n; ++i)
g << sol[i] << '\n';
return 0;
}