Cod sursa(job #1266006)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 18 noiembrie 2014 04:58:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <cstdio>
#include <iostream>
#include <vector>

struct Interval {
    int left, right;
    Interval(int left, int right): left(left), right(right) {}
    bool contains(int value)
    {
        return left <= value and value < right;
    }
    bool has_children()
    {
        return left+1<right;
    }
    Interval leftHalf()
    {
        return Interval(left, (left+right)>>1);
    }
    Interval rightHalf()
    {
        return Interval((left+right)>>1, right);
    }
    bool contains(Interval interval)
    {
        return this->left <= interval.left and interval.right <= this->right;
    }
    int size()
    {
        return right - left;
    }
};

struct Nod
{
    int value;
    Interval interval;
    Nod *left, *right;
    Nod(Interval interval, int value): 
        value(value), 
        interval(interval),
        left(NULL), 
        right(NULL){}
} *root;

Nod* build_tree(Interval interval)
{
    Nod *ret = new Nod(interval, interval.size());
    if(interval.has_children()) {
        ret->left = build_tree(interval.leftHalf());
        ret->right = build_tree(interval.rightHalf());
    }
    return ret;
}

void remove(Nod* node, int which)
{
    node->value--;
    if(node->interval.has_children())
    {
        if(node->interval.leftHalf().contains(which))
        {
            remove(node->left, which); 
        }
        else
        {
            remove(node->right, which);
        }
    }
}

int kth_element(Nod* node, int kth)
{
    if(!(node->interval.has_children())) {
        return node->interval.left;
    }

    if(node->left->value >= kth) {
       return kth_element(node->left, kth); 
    }

    return kth_element(node->right, kth - node->left->value);
}

int main ()
{

    FILE *fin = fopen("order.in", "r");
    FILE *fout = fopen("order.out", "w");
    int n;
    fscanf(fin, "%d", &n);
    root = build_tree(Interval(1,n+1));

    int pos=1; // pozitia in elementele existente
    for(int k=1; k<n; k++)
    {

        pos = (pos+k-1) % (n-k+1) + 1; // salt in elementele care exista
        int element = kth_element(root, pos);
        fprintf(fout,"%d ", element);
        remove(root, element);
        pos = ( pos -1 -1 + n-k) % (n-k) +1;
    }
    fprintf(fout,"%d",kth_element(root,1));
    return 0;
}