battle_exercises_2.cpp

#include <iostream>

using namespace std;

const int MAX_AMOUNT = 100000;
const int NOT_LEAF = -1;

pair<int, int> segment_tree[4 * MAX_AMOUNT];
int current_index = 1; // Этой контсантой даем листьям номера

/**
 * Строит сегментное дерево, у которого в каждом узле хранится, сколько в его детях содержится непосчитанных элементов
 *
 * @param key          - ключ текущего узла в массиве
 * @param left_index   - левая граница дерева
 * @param right_index  - правая граница дерева
 */
void buildSegmentTree(int key, int left_index, int right_index) {
  // Если индексы сходятся - то ты лист
  if (left_index == right_index) {
    segment_tree[key] = make_pair(1, current_index++);
    return;
  }

  int middle_index = (left_index + right_index) / 2;
  int left_children_key = 2 * key;
  int right_children_key = 2 * key + 1;

  // Строим детей
  buildSegmentTree(left_children_key, left_index, middle_index);
  buildSegmentTree(right_children_key, middle_index + 1, right_index);

  // Сумма текущего узла - сумма его детей, и также помечаем, что не лист
  segment_tree[key].first = segment_tree[left_children_key].first + segment_tree[right_children_key].first;
  segment_tree[key].second = NOT_LEAF;
}

/**
 * Достает индекс элемента, который лежит на расстоянии @param needed_amount от начала массива
 *
 * @param key           - ключ текущего узла в массиве
 * @param left_index    - левая граница дерева
 * @param right_index   - правая граница дерева
 * @param needed_amount - необходимая сумма
 */
int getElement(int key, int left_index, int right_index, int needed_amount) {
  // Если дошли ло листа - "гасим" его и отдаем его индекс
  if (left_index == right_index) {
    segment_tree[key].first--;
    return segment_tree[key].second;
  }

  // Уменьшаем значение узла, чтобы не перестраивать после
  segment_tree[key].first--;

  int middle_index = (left_index + right_index) / 2;
  int left_children_key = 2 * key;
  int right_children_key = 2 * key + 1;

  int amount_in_left_tree = segment_tree[left_children_key].first;

  // Если нашли больше, чем нужно - идем копаться в левое дерево, если нашли меньше - ищем в правом остатки
  if (amount_in_left_tree >= needed_amount) {
    return getElement(left_children_key, left_index, middle_index, needed_amount);
  } else {
    return getElement(right_children_key, middle_index + 1, right_index, needed_amount - amount_in_left_tree);
  }
}

/**
 * Решает задачу 1521 - "Военные учения 2"
 * @link http://acm.timus.ru/problem.aspx?space=1&num=1521
 *
 * @param total_amount
 * @param step
 */
void solveBattleExercises2(int total_amount, int step) {
  buildSegmentTree(1, 1, MAX_AMOUNT);

  int needed_amount = step;
  for (int i = 0; i < total_amount; i++) {
    int next_index = getElement(1, 1, MAX_AMOUNT, needed_amount);
    cout << next_index << " ";

    if (i == total_amount - 1) {
      break;
    }

    // Находим, сколько нам необходимо иметь единиц на текущей итерации. % (left_amount) помогает делать цикличность
    needed_amount = (needed_amount - 1 + step) % (total_amount - 1 - i);
    if (needed_amount == 0) {
      needed_amount += total_amount - 1 - i;
    }
  }
}

int main() {
  int n;
  int k;

  cin >> n >> k;
  solveBattleExercises2(n, k);
}