Pagini recente » Cod sursa (job #2730022) | Cod sursa (job #541969) | Cod sursa (job #976270) | Cod sursa (job #220634) | Cod sursa (job #529267)
Cod sursa(job #529267)
// 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 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);
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);
}