Pagini recente » Cod sursa (job #3002508) | Cod sursa (job #413323) | Cod sursa (job #1400454) | Cod sursa (job #810681) | Cod sursa (job #2970128)
#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 search(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);
}
}
if(ans==n)
ans--;
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.search(poz);
aib.update(who,-1);
vultur<<who<<" ";
}
vultur<<'\n';
return 0;
}