Pagini recente » Cod sursa (job #2053275) | Cod sursa (job #2829100) | Cod sursa (job #1020223) | Cod sursa (job #1251556) | Cod sursa (job #532860)
Cod sursa(job #532860)
// 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); // cautare binara
int main() {
int position;
in >> lenght;
for(int i=1;i<=lenght;i++) {
in >> person[i]; // locul ocupat in clasamentul intermediar
add(i,1);
}
// se iau toti concurentii in ordine inversa
for(int i=lenght;i>=1;i--) {
// se determina pozitia acestuia in clasament (cautare binara)
position = search(person[i]);
// concurentul respectiv va ocupa pozitia aceasta
place[position] = i;
// aceasta pozitie este stearsa din pozitiile disponibile
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)) // daca exista o pozitie mai "mica" cu aceeasi valoare a sumei
right = middle-1;
else
return middle;
else
if(answer > toBeFound)
right = middle-1;
else
left = middle+1;
}
}