Pagini recente » Cod sursa (job #3189322) | Cod sursa (job #2761897) | Cod sursa (job #786199) | Cod sursa (job #1975419) | Cod sursa (job #826753)
Cod sursa(job #826753)
#include <fstream>
#define MAX_SIZE 30001
using namespace std;
ifstream input("schi.in");
ofstream output("schi.out");
typedef struct
{
int value;
int pos;
}st;
st tree[3 * MAX_SIZE];
int vect[MAX_SIZE];
void build_tree(int nod , int left , int right)
{
if (left == right)
{
tree[nod].value = vect[left];
tree[nod].pos = left;
return;
}
int middle = (left + right) / 2;
build_tree(2*nod , left , middle);
build_tree(2*nod+1 , middle+1 , right);
if (tree[2*nod+1].value <= tree[2*nod].value)
{
tree[nod] = tree[2*nod+1];
}
else
{
tree[nod] = tree[2*nod];
}
}
void update_tree(int nod , int left , int right , int A , int B,int val)
{
if (A > B) return;
if (left == right)
{
tree[nod].value += val;
return;
}
int middle = (left + right) / 2;
if (A <= middle) update_tree(2*nod , left , middle , A , B , val);
if (middle < B) update_tree(2 * nod +1 ,middle+1,right , A , B, val);
if (tree[2*nod+1].value <= tree[2*nod].value)
{
tree[nod] = tree[2*nod+1];
}
else
{
tree[nod] = tree[2*nod];
}
}
int main()
{
int N;
input >> N;
for (int i = 1;i<=N;i++)
{
input >> vect[i];
}
build_tree(1,1,N);
for (int i = 1 ; i<=N;i++)
{
output << tree[1].pos << "\n";
update_tree(1,1,N,1,tree[1].pos-1,1);
update_tree(1,1,N,tree[1].pos,tree[1].pos,MAX_SIZE);
/*output << "Iteratia " << i << " ---- \n";
for (int j = 1; j<= 15;j++)
{
output << tree[j].value << " " << tree[j].pos << "\n";
}*/
}
input.close();
output.close();
return 0;
}