Pagini recente » Cod sursa (job #1279710) | Cod sursa (job #566159) | Cod sursa (job #1240262) | Cod sursa (job #3020935) | Cod sursa (job #3350223)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n;
void update(vector<int> &aib, int i, int v){
while(i <= n){
aib[i] += v;
i += i&(-i);
}
}
int query(vector<int> &aib, int i){
int s = 0;
while(i > 0){
s += aib[i];
i -= i&(-i);
}
return s;
}
int kth(vector<int> &aib, int k){
int l = 1, r = n;
int ans = -1;
while(l <= r){
int mid = l+(r-l)/2;
int tilmid = query(aib, mid);
if(tilmid > k){
r = mid-1;
}
else if(tilmid < k){
l = mid+1;
}
else{
ans = mid;
r = mid-1;
}
}
return ans;
}
void generateAIB(vector<int> &aib, vector<int> &v){
for(int i = 1; i<=n; i++){
update(aib, i, v[i]);
}
}
int main(){
fin >> n;
vector<int> v(n+1, 1);
vector<int> aib(n+1, 0);
int poz = 1;
generateAIB(aib, v);
for(int i = 1; i<=n; i++){
int remaining = n-i+1;
int rang_poz = query(aib, poz);
int rang_tinta = (rang_poz + i)%remaining;
if(rang_tinta == 0) rang_tinta = remaining;
poz = kth(aib, rang_tinta);
update(aib, poz, -1);
fout << poz << ' ';
}
return 0;
}