gistfile1.java

package ru.spbau.turaev.timus1521;

import java.util.Random;
import java.util.Scanner;


class Node {
    Node(int x, long y, Node left, Node right) {
        this.x = x;
        this.y = y;
        this.right = right;
        this.left = left;
        size = 1;
    }

    public void recalc() {
        size = sizeOf(left) + sizeOf(right) + 1;
    }

    private static int sizeOf(Node node) {
        return node == null ? 0 : node.size;
    }

    public Pair<Node> split(int x) {
        Node newNode = null;

        int curIndex = sizeOf(left) + 1;
        if (curIndex <= x) {
            Node r;
            if (right == null)
                r = null;
            else {
                Pair<Node> split = right.split(x - curIndex);
                newNode = split.first;
                r = split.second;
            }
            this.right = newNode;
            this.recalc();
            return new Pair<Node>(this, r);
        } else {
            Node l;
            if (left == null)
                l = null;
            else {
                Pair<Node> split = left.split(x);
                l = split.first;
                newNode = split.second;
            }
            this.left = newNode;
            this.recalc();
            return new Pair<Node>(l, this);
        }
    }

    public Node left;
    public Node right;
    public int x;
    public long y;
    public int size;
}

class Pair<A> {
    public A first;
    public A second;

    Pair(A first, A second) {
        this.first = first;
        this.second = second;
    }
}

class Treap {
    private static Random random = new Random();

    private Node root;

    public void append(int x) {
        Node r = new Node(x, random.nextLong(), null, null);
        root = merge(root, r);
    }

    public void removeAndRotate(int pos) {
        Pair<Node> split1 = root.split(pos);
        Node l = split1.first;
        Node r = split1.second;

        Pair<Node> split2 = r.split(1);
        Node m = split2.first;
        r = split2.second;

        System.out.println(m.x);
        root = merge(r, l);
    }

    private static Node merge(Node a, Node b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }

        if (b.y > a.y) {
            b.left = merge(a, b.left);
            b.recalc();
            return b;
        } else {
            a.right = merge(a.right, b);
            a.recalc();
            return a;
        }
    }

}


public class Main {
    public static void main(String[] args) {
        Treap treap = new Treap();

        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int K = input.nextInt();

        for (int i = 1; i <= N; i++) {
            treap.append(i);
        }

        int curSize = N;

        K--;
        for (int i = 0; i < N; i++) {
            treap.removeAndRotate(K % curSize);
            curSize--;
        }
    }
}