Pagini recente » Cod sursa (job #2729464) | Cod sursa (job #1886783) | Cod sursa (job #1698071) | Cod sursa (job #382028) | Cod sursa (job #2413693)
#include <bits/stdc++.h>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
namespace Treap{
struct Node{
Node *l=0,*r=0;
int x=0;
int y=0;
int sz=0;
Node (int _x=0): x(_x), y(rand()), sz(1) {}
void recalc();
};
int cnt(Node* t){
if(!t)return 0;
return (t->sz);
}
void Node::recalc(){
sz=cnt(l)+cnt(r)+1;
}
pair<Node*,Node*> split(Node* t,int k){
if(!t)return {};
t->recalc();
if(cnt(t->l)>=k){
auto pa=split(t->l,k);
t->l=pa.second;
t->recalc();
return {pa.first,t};
}else{
auto pa=split(t->r,k-cnt(t->l)-1);
t->r=pa.first;
t->recalc();
return {t,pa.second};
}
}
Node* join(Node* l,Node *r){
if(!l)return r;
if(!r)return l;
l->recalc();
r->recalc();
if(l->y > r->y)
{
l->r=join(l->r,r);
l->recalc();
return l;
}else{
r->l=join(l,r->l);
r->recalc();
return r;
}
}
Node* insert(Node* t,int k,int e){
auto pa=split(t,k-1);
return join(pa.first,join(new Node(e),pa.second));
}
Node* erase(Node* t,int k){
auto pa=split(t,k-1);
auto u =split(pa.second,1);
return join(pa.first,u.second);
}
int acces(Node* t,int k){
if(!t)return -1;
t->recalc();
if(cnt(t->l)+1==k) return (t->x);
if(cnt(t->l)>=k) return acces(t->l,k);
return acces(t->r,k-cnt(t->l)-1);
}
}
int main()
{
srand(time(0));
Treap::Node *root=0;
int n;f>>n;
for(int i=1;i<=n;i++)
root=Treap::insert(root,i,i);
int lastpoz=1;
for(int i=1;i<=n;i++)
{
lastpoz+=i;
// while(lastpoz>n-i+1)
// lastpoz-=n-i+1;
lastpoz=(lastpoz-1)%(n-i+1)+1;
g<<Treap::acces(root,lastpoz)<<' ';
root=Treap::erase(root,lastpoz);
lastpoz--;
}
return 0;
}