Cod sursa(job #1847471)

Utilizator dan89Stan Alexandru dan89 Data 14 ianuarie 2017 17:31:56
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#define in "order.in"
#define out "order.out"

struct tree {
    tree *left;
    tree *right;
    int st;
    int dr;
    int id;
    int count;
};

tree* initTree(tree *node, int left, int right) {
    if (node == NULL) {
        node = new tree;
        node->left = NULL;
        node->right = NULL;
        node->st = left;
        node->dr = right;
    }

    if (node->st==node->dr) {
        node->id=node->st;
        node->count = 1;
        return node;
    }

    int mid = (node->st + node->dr) / 2;

    node->left = initTree(node->left, node->st, mid);
    node->right = initTree(node->right, mid+1, node->dr);

    node->count = node->left->count + node->right->count;

    return node;
}

int removeChild(tree *node, int n) {
    node->count--;

    if (node->left == NULL && node->right == NULL) {
        return node->id;
    }

    if (node->left->count >= n) {
        return removeChild(node->left, n);
    } else {
        return removeChild(node->right, n - node->left->count);
    }
}

int main() {
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);

    tree *root = NULL;

    int N;
    scanf("%d", &N);

    root = initTree(root, 1, N);

    int c = 1;

    for (int i = 1; i<=N; i++) {
        c += i;
        c %= root->count;
        if (!c) c = root->count;
        printf("%d ", removeChild(root, c));
        c--;
    }

    return 0;
}