Pagini recente » Cod sursa (job #2148933) | Cod sursa (job #2099150) | Cod sursa (job #1357914) | Cod sursa (job #1635856) | Cod sursa (job #2099178)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
const int N = 30001;
int v[N], sol[N], aib[N];
int n;
int lsd(int x){
return x & (x ^ (x-1));
}
void update(int index, int value){
if(index < N){
aib[index] += value;
update(index + lsd(index), value);
}
}
void print_aib(){
for(int i=1; i<=n; ++i)
cout<<aib[i]<<" "; cout<<"\n";
}
int query(int dr){ /// [1, dr]
int index = dr;
int sum = 0;
while(index > 0){
sum += aib[index];
index -= lsd(index);
}
return sum;
}
int query_interval(int st, int dr){ /// [st, dr]
return query(dr) - query(st-1);
}
int firstIndexOf(int x){
int st = 1;
int dr = n;
while(st < dr){
int mij = (st+dr) / 2;
int value = query(mij);
if(x <= value) /// Keep looking (left)
dr = mij;
else if(x > value) /// Keep looking (right)
st = mij+1;
}
if(query(st) != x)
return -1;
else{ /// FIXME: Binary search this value!
while(query(st-1) == x)
--st;
return st;
}
}
int main()
{
/*n = 8;
update(1, 1);
update(4, 1);
for(int i=1; i<=n; ++i)
cout<<"[1, "<<i<<"] = "<<query(i)<<"\n";
for(int i=1; i<=query(n); ++i)
cout<<i<<" --> "<<firstIndexOf(i)<<"\n";
return 0;*/
in>>n;
for(int i=1; i<=n; ++i)
in>>v[i];
for(int i=1; i<=n; ++i)
update(i, 1);
for(int i=n; i>=1; --i)
{
//if(i%100 == 0) cout<<i<<"\n";
int index = firstIndexOf(v[i]);
//cout<<i<<" --> "<<index<<"\n";
sol[index] = i;
update(index, -1);
}
for(int i=1; i<=n; ++i)
out<<sol[i]<<"\n";
/*update(1, 1);
update(2, 1);
update(5, 1);
update(7, 1);
for(int i=1; i<=n; ++i)
cout<<"[1, "<<i<<"] = "<<query(i)<<"\n";
for(int i=1; i<=query(n); ++i)
cout<<i<<" --> "<<firstIndexOf(i)<<"\n";*/
return 0;
}