Pagini recente » Cod sursa (job #877034) | Cod sursa (job #2901160) | Cod sursa (job #3000797) | Cod sursa (job #1941210) | Cod sursa (job #2970134)
#include <bits/stdc++.h>
using namespace std;
ifstream gaina("order.in");
ofstream vultur("order.out");
const int nmax=100000;
int lsb(int x) {return x&(-x);}
struct AIB {
int aib[nmax+1],n;
void update(int poz,int val) {
for(; poz<=n; poz+=lsb(poz))
aib[poz]+=val;
}
int queryPref(int poz) {
int s=0;
for(; poz>0; poz-=lsb(poz))
s+=aib[poz];
return s;
}
int query(int st,int dr) {
return queryPref(dr)-queryPref(st-1);
}
int searchX(int x) {
if(x==0)
x=1;
int s=0,ans=0;
for(int i=20; i>=0; i--) {
if(ans+(1<<i)<=n && s+aib[ans+(1<<i)]<x) {
s+=aib[ans+(1<<i)];
ans+=(1<<i);
}
}
return ans+1;
}
};
int main() {
AIB aib;
int n,rem,poz,who=-1;
gaina>>n;
aib.n=n;
for(int i=1; i<=n; i++)
aib.update(i,1);
rem=n;
poz=1;
for(int pas=1; pas<=n; pas++) {
poz=aib.queryPref(poz)+pas;
if(poz>rem&&rem>0)
poz%=rem;
rem--;
who=aib.searchX(poz);
aib.update(who,-1);
vultur<<who<<" ";
}
return 0;
}