Pagini recente » Cod sursa (job #953457) | Cod sursa (job #236979) | Diferente pentru home intre reviziile 412 si 411 | Istoria paginii grigore-moisil-2017/clasament/9 | Cod sursa (job #229892)
Cod sursa(job #229892)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const char iname[] = "schi.in";
const char oname[] = "schi.out";
#define getc(n) (n->cnt = (!n->el) + (n->l != NULL ? n->l->cnt : 0) + (n->r != NULL ? n->r->cnt : 0))
struct T {
int key, cnt, el;
T *l, *r;
T(int key) {
this->key = key, l = r = NULL;
cnt = el = 0;
}
} *R;
void insert(T* &n, int lo, int hi)
{
if (hi < lo) return ;
int mid = (hi + lo) >> 1;
n = new T(mid);
insert(n->l, lo, mid - 1);
insert(n->r, mid + 1, hi);
getc(n);
}
void lookup(T* &n, int cnt, int el)
{
if (cnt <= (n->l != NULL ? n->l->cnt : 0))
lookup(n->l, cnt, el);
else {
if ((n->l != NULL ? n->l->cnt : 0) + (!n->el) == cnt)
n->el = el;
else
lookup(n->r, cnt - (n->l != NULL ? n->l->cnt : 0) - (!n->el), el);
}
getc(n);
}
void print(T* &n) {
if (n == NULL) return ;
print(n->l), printf("%d\n", n->el), print(n->r);
}
int main(void)
{
srand(unsigned(time(NULL)));
R = NULL;
freopen(iname, "r", stdin);
int V[30000];
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf("%d", &V[i]);
insert(R, 0, n - 1);
for (int i = n - 1; i >= 0; -- i) lookup(R, V[i], i + 1);
freopen(oname, "w", stdout);
print(R);
return 0;
}