Pagini recente » Cod sursa (job #1847148) | Istoria paginii runda/simulare_iiot_2019-2020_runda_3 | Cod sursa (job #2675006) | Cod sursa (job #1469671) | Cod sursa (job #529285)
Cod sursa(job #529285)
// http://infoarena.ro/problema/schi
// rezolvata folosind arbori indexati binar (http://infoarena.ro/aib)
#include <fstream>
using namespace std;
#define maxSize 30002
#define zeros(x) ( (x ^ (x - 1)) & x )
int lenght;
int AIB[maxSize],person[maxSize],place[maxSize];
ifstream in("schi.in");
ofstream out("schi.out");
void add(int location,int value); // adauga la position "location" valoarea "value"
int query(int right); // returneaza suma subsecventei [1,right]
int search(int toBeFound);
int main() {
int position;
in >> lenght;
for(int i=1;i<=lenght;i++) {
in >> person[i]; // locul ocupat in clasamentul intermediar
add(i,1);
}
for(int i=lenght;i>=1;i--) {
position = search(person[i]);
place[position] = i;
add(position,-1);
}
for(int i=1;i<=lenght;i++)
out << place[i] << "\n";
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 toBeFound) {
int left = 1,right = lenght;
int middle,answer = 0;
for(;;) {
middle = (left + right) / 2;
answer = query(middle);
if(answer == toBeFound)
if(answer == query(middle-1))
right = middle-1;
else
return middle;
else
if(answer > toBeFound)
right = middle-1;
else
left = middle+1;
}
}