Pagini recente » Cod sursa (job #594714) | Cod sursa (job #2985399) | Cod sursa (job #721212) | Cod sursa (job #2824922) | Cod sursa (job #1287456)
#include <fstream>
#include <vector>
using namespace std;
ifstream is("schi.in");
ofstream os("schi.out");
int n, answ, sum;
int poz, val;
int lt, rt;
vector<short> v, a, q;
void UPDATE(int nod, int st, int dr);
void SUM(int nod, int st, int dr);
int main()
{
is >> n;
v.resize(n + 1);
a.resize(4 * n);
q.resize(n + 1);
val = 1;
for ( int i = 1; i <= n; ++i )
{
is >> v[i];
poz = i;
UPDATE(1, 1, n);
}
int st, dr, md;
lt = 1;
val = 0;
for ( int i = n; i; --i )
{
st = 1, dr = n;
answ = 0;
do
{
md = ( st + dr ) / 2;
rt = md;
sum = 0;
SUM(1, 1, n);
if ( sum >= v[i] )
{
if ( sum == v[i] && !q[md] )
answ = md, st = dr + 1;
else
dr = md - 1;
}
else
st = md + 1;
} while ( st <= dr );
q[answ] = i;
poz = answ;
UPDATE(1, 1, n);
}
for ( int i = 1; i <= n; ++i )
os << q[i] << "\n";
is.close();
os.close();
return 0;
}
void UPDATE(int nod, int st, int dr)
{
if ( st == dr )
{
a[nod] = val;
return;
}
int md = ( st + dr ) / 2;
if ( poz <= md )
UPDATE(2 * nod, st, md);
else
UPDATE(2 * nod + 1, md + 1, dr);
a[nod] = a[2 * nod] + a[2 * nod + 1];
}
void SUM(int nod, int st, int dr)
{
if ( lt <= st && dr <= rt )
{
sum += a[nod];
return;
}
int md = ( st + dr ) / 2;
if ( lt <= md )
SUM(2 * nod, st, md);
if ( rt > md )
SUM(2 * nod + 1, md + 1, dr);
}