# Cod sursa(job #2750620)

Utilizator Data 12 mai 2021 15:27:14 Order 100 cpp-64 done Arhiva de probleme 2.58 kb
``````//#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define vi vector<int>
int nex[30005],pre[30005],f[30005],arb[500005];
ifstream cin("order.in");
ofstream cout("order.out");
vi brut(int n){
for(int i=1;i<=n;i++){
f[i]=0;
}
int cur=1;
for(int i=1;i<=n;i++){
int x=i;
while(x){
x--;
cur++;
if(cur==n+1)
cur=1;
if(f[cur]==1)
x++;
}
f[cur]=1;
cout<<cur<<" ";
}
cout<<"\n";
}
void create(int nod,int st,int dr){
arb[nod]=dr-st+1;
if(st==dr)
return;
create(nod*2,st,(st+dr)/2);
create(nod*2+1,(st+dr)/2+1,dr);
}
void upd(int nod,int st,int dr,int care){
if(st==dr){
arb[nod]--;
return;
}
int mid=(st+dr)/2;
if(mid>=care){
upd(nod*2,st,mid,care);
}
else{
upd(nod*2+1,mid+1,dr,care);
}
arb[nod]=arb[nod*2]+arb[nod*2+1];
}
int query_1(int nod,int st,int dr,int que){
if(st==dr){
return 1;
}
int mid=(st+dr)/2;
if(mid>=que){
return query_1(nod*2,st,mid,que);
}
return arb[nod*2]+query_1(nod*2+1,mid+1,dr,que);
}
int query_2(int nod,int st,int dr,int que){
if(st==dr){
return st;
}
int mid=(st+dr)/2;
if(arb[nod*2]>=que){
return query_2(nod*2,st,mid,que);
}
return query_2(nod*2+1,mid+1,dr,que-arb[nod*2]);
}
int go_next(int start,int how_many,int n){
int x=query_1(1,1,2*n,start);
x+=how_many;
int y=query_2(1,1,2*n,x);
return y;
}
int main()
{
int n;
ios_base::sync_with_stdio(false);
cin>>n;
//brut(n);
create(1,1,2*n);
for(int i=1;i<=n;i++){
nex[i]=i+1;
pre[i]=i-1;
if(i==1){
pre[i]=n;
}
if(i==n){
nex[i]=1;
}
}
//cout<<"step 1";
int cur=1;
for(int i=1;i<=n;i++){
int ciclu=i;
if(i==n){
break;
ciclu=2;
}
else
ciclu%=(n-i+1);
if(ciclu==0)
ciclu=n-i+1;
cur=nex[cur];
cur=go_next(cur,ciclu-1,n);
if(cur>n)
cur-=n;
upd(1,1,2*n,cur);
upd(1,1,2*n,cur+n);
/*
for(int j=1;j<=ciclu;j++){
cur=nex[cur];
}
cout<<cur<<" ";
*/
nex[pre[cur]]=nex[cur];
pre[nex[cur]]=pre[cur];
cout<<cur<<" ";
}
cout<<query_2(1,1,2*n,1);
return 0;
}
``````