Pagini recente » tema | Cod sursa (job #1894886) | Cod sursa (job #1850054) | Cod sursa (job #1673022) | Cod sursa (job #2409199)
#include <fstream>
#include <stdlib.h>
#include <time.h>
using namespace std;
ifstream fin ("order.in");
ofstream fout ("order.out");
int nr,i,n,nr_nodes,sol;
struct treap{
int val;
int priority;
int nr;
treap *left, *right;
treap (int val, int priority, treap *left, treap*right, int nr){
this->val = val;
this->priority = priority;
this->left = left;
this->right = right;
this->nr = nr;
}
};
treap *rad, *nil;
void get_nr (treap *rad){
rad->nr = rad->left->nr + rad->right->nr + 1;
}
void rotate_left (treap *&rad){
treap *aux = rad->left;
rad->left = aux->right;
aux->right = rad;
rad = aux;
get_nr (rad->right);
get_nr (rad);
}
void rotate_right (treap *&rad){
treap *aux = rad->right;
rad->right = aux->left;
aux->left = rad;
rad = aux;
get_nr (rad->left);
get_nr (rad);
}
void balance (treap *&rad){
if (rad->left != NULL && rad->left->priority > rad->priority)
rotate_left (rad);
else
if (rad->right != NULL && rad->right->priority > rad->priority)
rotate_right(rad);
}
void add_node (treap *&rad, int key, int priority){
if (rad == nil){
rad = new treap (key,priority,nil,nil,1);
nr_nodes++;
return;
} else {
if (rad->val > key)
add_node(rad->left,key,priority);
else
if (rad->val < key)
add_node(rad->right,key,priority);
}
balance (rad);
get_nr (rad);
}
inline void delete_node (treap *&rad, int key){
if (rad != nil){
if (rad->val > key)
delete_node (rad->left,key);
else{
if (rad->val < key)
delete_node (rad->right,key);
else { /// inseamna ca am gasit valoarea
if (rad->left == nil && rad->right == nil){ /// ins ca e frunza
delete rad;
rad = nil;
nr_nodes--;
} else {
if (rad->left->priority > rad->right->priority)
rotate_left (rad);
else rotate_right (rad);
delete_node (rad,key);
}
}
}
if (rad != nil) /// trebuie sa updatez iar mini, maxi si dif
get_nr (rad);
}
}
inline int query (treap *&rad, int nr){
if (rad->left->nr == nr-1)
return rad->val;
else{
if (rad->left->nr < nr)
return query (rad->right, nr-rad->left->nr-1);
else return query (rad->left,nr);
}
}
int main (){
srand( time(0) );
rad = nil = new treap (0,0,NULL,NULL,0);
fin>>n;
for (i=1;i<=n;i++)
add_node (rad,i,rand());
nr = 2;
for (i=0;i<n;i++){
nr += i;
nr %= (n-i);
if (nr == 0)
nr = n-i;
sol = query(rad,nr);
fout<<sol<<" ";
delete_node (rad,sol);
}
return 0;
}