Pagini recente » Cod sursa (job #1707214) | Cod sursa (job #1286562) | Cod sursa (job #521602) | Cod sursa (job #52605) | Cod sursa (job #529274)
Cod sursa(job #529274)
// http://infoarena.ro/problema/schi
#include <fstream>
using namespace std;
#define maxSize 30002
#define zeros(x) ( (x ^ (x - 1)) & x )
int lenght,i;
int AIB[maxSize],person[maxSize],place[maxSize];
ifstream in("schi.in");
ofstream out("schi.out");
void add(int location,int value);
int query(int right);
int search(int left,int right);
int cautare(int X)
{
int h,step;
for (step=1;step<=lenght;step<<=1);
step>>=1;
for (h=lenght;step;step>>=1)
if (h-step>=1 && query(h-step)>=X)
h-=step;
return h;
}
int main() {
int position;
in >> lenght;
for(i=1;i<=lenght;i++) {
in >> person[i]; // locul ocupat in clasamentul intermediar
add(i,1);
}
for(i=lenght;i>=1;i--) {
//position = search(1,lenght);
position = cautare(person[i]);
place[position] = i;
add(position,-1);
}
for(i=1;i<=lenght;i++)
out << place[i] << " ";
in.close();
out.close();
return (0);
}
void add(int location,int value) {
for(int k=location;k<=lenght;k=k+zeros(k))
AIB[k] = AIB[k] + value;
}
int query(int right) {
int value = 0;
for(int k=right;k>0;k=k-zeros(k))
value = value + AIB[k];
return value;
}
int search(int left,int right) {
int middle = (left + right) / 2;
int answer = query(middle);
if(answer == person[i])
//if(query(middle-1) != query(middle))
return middle;
//else
//return search(left,middle-1);
else
if(answer > person[i])
return search(left,middle-1);
else
return search(middle+1,right);
}