Pagini recente » Cod sursa (job #3177541) | Cod sursa (job #813606) | Cod sursa (job #3308743) | Cod sursa (job #618125) | Cod sursa (job #3350222)
#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, remaining = n;
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;
int eliminat = kth(aib, rang_tinta);
fout << eliminat << ' ';
update(aib, eliminat, -1);
poz = eliminat;
}
return 0;
}