Pagini recente » Cod sursa (job #1775941) | Cod sursa (job #1599569) | Cod sursa (job #2535302) | Cod sursa (job #1502357) | Cod sursa (job #2507316)
#include <fstream>
#include <random>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
typedef struct treap* arb;
mt19937 rnd((long long)(new char));
arb gol;
struct treap
{
int val;
int size;
long long prio;
treap *st, *dr;
void updSize()
{
size = 1 + st->size + dr->size;
}
pair<arb,arb> split(int poz)
{
if (this == gol)
return {gol,gol};
if (st->size < poz)
{
auto rez = dr->split(poz-st->size-1);
dr = rez.first;
updSize();
return {this, rez.second};
}
else
{
auto rez = st->split(poz);
st = rez.second;
updSize();
return {rez.first,this};
}
}
arb ins(int poz, int v);
arb del(int poz);
int access(int poz);
treap(int v=0): val(v), size(1), prio(rnd()), st(gol), dr(gol) { }
};
arb join(arb x, arb y)
{
if (x == gol)
return y;
if (y == gol)
return x;
if (x->prio < y->prio)
{
arb rez = join(x,y->st);
y->st = rez;
y->updSize();
return y;
}
else
{
arb rez = join(x->dr,y);
x->dr = rez;
x->updSize();
return x;
}
}
int n;
int main()
{
gol = new treap();
gol->prio = 0;
gol->size = 0;
gol->st = gol->dr = gol;
arb t = gol;
fin >> n;
for (int i=1;i<=n;i++)
t = t->ins(i,i);
int poz=1;
int runde = n;
int elim=0;
for (int i=1;i<=runde;i++)
{
poz += i;
poz %= n;
if (poz == 0)
poz = n;
fout << t->access(poz) << ' ';
t = t->del(poz);
poz--;
n--;
}
return 0;
}
arb treap::ins(int poz, int v)
{
auto rez = split(poz-1);
arb nod = new treap(v);
rez.first = join(rez.first,nod);
return join(rez.first,rez.second);
}
arb treap::del(int poz)
{
auto rez = split(poz);
auto aux = rez.first->split(poz-1);
return join(aux.first,rez.second);
}
int treap::access(int poz)
{
if (poz == st->size+1)
return val;
if (poz <= st->size)
return st->access(poz);
return dr->access(poz-st->size-1);
}