Pagini recente » Cod sursa (job #138902) | Cod sursa (job #1603169) | Cod sursa (job #410681) | Cod sursa (job #414123) | Cod sursa (job #2924203)
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int fen[30000],n;
void add(int nr,int pos){
for(int i = pos;i < n;i|=(i + 1)){
fen[i]+=nr;
}
}
int get(int pos){
int r = 0;
for(int i = pos;i >= 0;i&=(i + 1),i--){
r+=fen[i];
}
return r;
}
int range(int l,int r){
return get(r) - get(l - 1);
}
int bs(int l,int r,int pos,int moves){
if(l == r)return l;
int mij = (l + r)/2;
int nr;
if(pos + mij < n){
nr = range(pos,pos + mij);
}else{
nr = range(pos,n - 1) + range(0,pos + mij - n);
}
if(nr >= moves)return bs(l,mij,pos,moves);
else return bs(mij + 1,r,pos,moves);
}
int main()
{
int cnt = 0,i,cur = 0;
fin>>n;
for(i = 0;i < n;i++){
add(1,i);
}
for(i = 0;i < n;i++){
int moves = (i + 1)%(n - i);
if(moves == 0)moves = n - i;
///range (i,n - 1] + [1,i - 1)
int nr = bs(0,n,(cur + 1)%n,moves);
cur+=(nr + 1);
cur%=n;
fout<<cur%n + 1<<' ';
add(-1,cur);
}
return 0;
}