Pagini recente » Cod sursa (job #2907621) | Cod sursa (job #2181009) | Cod sursa (job #1191569) | Cod sursa (job #987788) | Cod sursa (job #811225)
Cod sursa(job #811225)
#include <stdio.h>
#include <string.h>
#include <math.h>
#define fs (node) << 1
#define fd ((node) << 1) + 1
#define mid ((left + right) >> 1)
using namespace std;
const char infile[] = "schi.in";
const char outfile[] = "schi.out";
const int MAXN = 1 << 16;
struct Node {
int val;
short int pos;
Node() {
val = pos = 0;
}
} arb[MAXN];
int *v;
int N, a, b, val;
void read() {
FILE *f = fopen(infile, "rt");
fscanf(f, "%d", &N);
v = new int[MAXN];
for(int i = 1; i <= N; ++i)
fscanf(f, "%d", v + i);
fclose(f);
}
void buildTree(int node, int left, int right) {
if(left > right) return;
if(left == right) {
arb[node].val = v[left]; arb[node].pos = left;
return;
}
buildTree(fs, left, mid);
buildTree(fd, mid + 1, right);
if(arb[fd].val <= arb[fs].val) {
arb[node].val = arb[fd].val; arb[node].pos = arb[fd].pos;
}
else {
arb[node].val = arb[fs].val; arb[node].pos = arb[fs].pos;
}
}
void updateTree(int node, int left, int right) {
if(a > b) return;
if(a <= left && right <= b) {
arb[node].val += val; v[node] += val;
return;
}
if(a <= mid)
updateTree(fs, left, mid);
if( mid < b)
updateTree(fd, mid + 1, right);
if(arb[fd].val <= arb[fs].val) {
arb[node].val = arb[fd].val + v[node]; arb[node].pos = arb[fd].pos;
}
else {
arb[node].val = arb[fs].val + v[node]; arb[node].pos = arb[fs].pos;
}
}
void solve() {
FILE *f = fopen(outfile, "wt");
buildTree(1, 1, N);
memset(v, 0, N * sizeof(v));
for(int i = 1; i <= N; ++i) {
fprintf(f, "%d\n", arb[1].pos);
a = 1; b = arb[1].pos - 1; val = 1; updateTree(1, 1, N);
a = b = arb[1].pos; val = MAXN; updateTree(1, 1, N);
}
}
int main() {
read();
solve();
return 0;
}