Pagini recente » Cod sursa (job #536194) | Cod sursa (job #995210) | Cod sursa (job #1193268) | Cod sursa (job #3132194) | Cod sursa (job #826795)
Cod sursa(job #826795)
#include <fstream>
#include <cstdlib>
#include <cstdio>
#define MAX_SIZE 1 << 16
#define left_son ((nod) << 1)
#define right_son ((nod) << 1) +1
using namespace std;
typedef struct
{
int value;
short int pos;
}st;
st tree[MAX_SIZE];
int A;
int B;
int N;
int val;
int *vect;
void read_data()
{
FILE *input = fopen("schi.in","r");
fscanf(input,"%d",&N);
vect = new int[MAX_SIZE];
for (int i = 1 ; i<=N;i++)
{
fscanf(input,"%d",&vect[i]);
}
fclose(input);
}
void build_tree(int nod , int left , int right)
{
if (left == right)
{
tree[nod].value = vect[left];
tree[nod].pos = left;
vect[left] = 0;
return;
}
int middle = (left + right) >> 1;
build_tree(left_son , left , middle);
build_tree(right_son , middle+1 , right);
if (tree[right_son].value <= tree[left_son].value)
{
tree[nod] = tree[right_son];
}
else
{
tree[nod] = tree[left_son];
}
}
void update_tree(int nod , int left , int right)
{
if (A > B) return;
if (A <=left && right <= B)
{
tree[nod].value += val;
vect[nod] += val;
return;
}
int middle = (left + right) >> 1;
if (A <= middle) update_tree(left_son , left , middle);
if (middle < B) update_tree(right_son ,middle+1,right);
if (tree[right_son].value <= tree[left_son].value)
{
tree[nod].value = tree[right_son].value + vect[nod];
tree[nod].pos = tree[right_son].pos;
}
else
{
tree[nod].value = tree[left_son].value + vect[nod];
tree[nod].pos = tree[left_son].pos;
}
}
int main()
{
FILE *output = fopen("schi.out","w");
read_data();
build_tree(1,1,N);
for (int i = 1 ; i<=N;i++)
{
fprintf(output,"%d\n",tree[1].pos);
A = 1;
B = tree[1].pos-1;
val = 1;
update_tree(1,1,N);
A = tree[1].pos;
B = tree[1].pos;
val = MAX_SIZE;
update_tree(1,1,N);
}
fclose(output);
return 0;
}