Любви к Python3 псто

2791_class.py

# Edit 1: Use faster I/O
import random
import sys

class ImplicitNode:
    def __init__(self, y, data):
        self.y = y
        self.data = data
        self.left = None
        self.right = None
        self.size = 0

def update(t):
    left_size = 0
    if t.left is not None:
        left_size = t.left.size
    right_size = 0
    if t.right is not None:
        right_size = t.right.size
    t.size = 1 + left_size + right_size

def split(t, k, add = 0):
    if t is None:
        return (None, None)
    left_size = 0
    if t.left is not None:
        left_size = t.left.size
    cur_key = add + left_size
    if cur_key >= k:
        t1, t2 = split(t.left, k, add)
        t.left = t2
        update(t)
        return (t1, t)
    else:
        t1, t2 = split(t.right, k, cur_key + 1)
        t.right = t1
        update(t)
        return (t, t2)

def merge(t1, t2):
    if t1 is None:
        return t2
    if t2 is None:
        return t1
    if t1.y > t2.y:
        t1.right = merge(t1.right, t2)
        update(t1)
        return t1
    else:
        t2.left = merge(t1, t2.left)
        update(t2)
        return t2

def create(key):
    return ImplicitNode(random.random(), key)

output = []

def printLTR(T):

    if T is None:
        return
    printLTR(T.left)
    global output
    output.append(T.data)
    printLTR(T.right)


def add(T, key):
    t1, t2 = split(T, key)
    t2 = merge(create(key), t2)
    return merge(t1, t2)


def moveToFront(T, a, b):
    t1, t2 = split(T, a - 1)
    t2, t3 = split(t2, b + 1 - a)
    t1 = merge(t2, t1)
    return merge(t1, t3)

in_data = sys.stdin.readlines()
n, m = map(int, in_data[0].split())

tree = create(1)

for i in range(n - 1):
    tree = add(tree, i + 2)

for k in range(m):
    a, b = map(int, in_data[k + 1].split())
    tree = moveToFront(tree, a, b)

printLTR(tree)
sys.stdout.write(' '.join(map(str, output)))

2791_list.py

# Edit 1: Use faster I/O
from random import random
import sys


def new_node(val):
    # y, sz, val, left, right
    return [random(), 1, val, -1, -1]


def get_sz(t):
    if t == -1:
        return 0
    return nodes[t][1]


def upd_sz(t):
    if t == -1:
        return
    nodes[t][1] = 1 + get_sz(nodes[t][3]) + get_sz(nodes[t][4])


def merge(t1, t2):
    if t1 == -1:
        return t2
    if t2 == -1:
        return t1
    if nodes[t1][0] > nodes[t2][0]:
        nodes[t1][4] = merge(nodes[t1][4], t2)
        upd_sz(t1)
        return t1
    else:
        nodes[t2][3] = merge(t1, nodes[t2][3])
        upd_sz(t2)
        return t2


def split(t, x):
    if t == -1:
        return (-1, -1)
    left_size = get_sz(nodes[t][3])
    if left_size < x:
        t1, t2 = split(nodes[t][4], x - left_size - 1)
        nodes[t][4] = t1
        upd_sz(t)
        return (t, t2)
    else:
        t1, t2 = split(nodes[t][3], x)
        nodes[t][3] = t2
        upd_sz(t)
        return (t1, t)


def to_front(t, l, r):
    t1, t2 = split(t, r + 1)
    t3, t4 = split(t1, l)
    return merge(merge(t4, t3), t2)


def create_tree(n):
    global nodes
    t = -1
    for i in range(n):
        nodes.append([random(), 1, i + 1, -1, -1])
        t = merge(t, i)
    return t


def print_tree(t):
    if t == -1:
        return
    print_tree(nodes[t][3])
    global output
    output.append(nodes[t][2])
    #print(nodes[t][2], end=' ')
    print_tree(nodes[t][4])

output = []

in_data = sys.stdin.readlines()
n, m = map(int, in_data[0].split())
nodes = []
t = create_tree(n)
for i in range(m):
    a, b = map(int, in_data[i + 1].split())
    t = to_front(t, a - 1, b - 1)
print_tree(t)
sys.stdout.write(' '.join(map(str, output)))

2791_naive.py

# Non-treap soultion for mccme_2791
# Edit #1: Use faster I/O
import sys

in_data = sys.stdin.readlines()

n, m = map(int, in_data[0].split())
soldiers = [i + 1 for i in range(n)]

for order in range(m):
    a, b = map(int, in_data[order + 1].split())
    a, b = a - 1, b - 1
    soldiers = soldiers[a : b + 1] + soldiers[:a] + soldiers[b + 1:]
    #print(soldiers)

sys.stdout.write(' '.join(map(str, soldiers)))

README.md

О реализации декартовых деревьев в Python3

Язык Python очень хорош и приятен для программирования, однако некоторые задачи в нём будут выполняться дольше, чем хотелось бы. Критический для написания многих программ вопрос - "насколько дольше?". В данном gist'е я попытаюсь сравнить время выполнения трёх программ, решающих одну и ту же задачу (№2791 "В начало строя!" с informatics.mccme.ru).

Первая программа будет реализовывать дерево "явно", используя класс ImplicitNode для хранения узла дерева. Для доступа к потомкам будут использоваться ссылки.

Вторая программа будет хранить дерево в виде списка списков - в списке nodes будут храниться списки по 5 элементов каждый, в котором уже будут храниться все данные узла. Вместо ссылок будут использованы индексы в списке nodes.

Третья программа - "наивное" решение задачи. Деревья не используются, используются слайсы в списках. Это решение приведено как "контрольное".

Оценивание

К сожалению, полноценного локального тестирования я не проводил (хотя это было бы, наверное, достаточно занятно и произвело бы на свет несколько красивых графиков). Вместо этого я ограничился отсыланием задачи на informatics и подсчётом верно проиденных тестов. Допускаются тесты, на которых превышается время тестирования, не допускаются тесты с неправильным ответом

Результаты

   Программа     |  Количество тестов
2791_class.py    |         9
2791_list.py     |        11
2791_naive.py    |        13

Комментарии

Очевидно, результаты можно было бы улучшить: так, вариант решения 2791_list.py, использующий map(int, input().split()), работает медленнее, чем предложенный. Вполне возможно, что допустимы и другие "оптимизации". Однако необходимость прибегать к неочевидным ходам, необходимость делать код менее очевидным и более запутанным, кажется, подрывает самую главную идею написания кода на данном языке (краткость и очевидность).

Тем не менее, буду признателен за любые комментарии, подкреплённые более производительным (проходящим большее количество тестов) кодом.