Відновити цикли#12783

Відновити цикли (Розбір)

Автор задачі:

Мар'ян Шийка

Підготував:

Мар'ян Шийка

Розбір:

Мар'ян Шийка

Ідея

Кінцевий рахунок людини дорівнює максимальному значенню $a_{j}$ a_j серед усіх позицій, які вона відвідає за $x$ кроків.

Спочатку перевіримо, чи відповідь взагалі може існувати. Якщо для хоча б однієї людини, яка починає на позиції $s$ , виконується

a_{s} > c,

a_s>c,

то вже на першому кроці її рахунок стане більшим за потрібне значення $c$ . У такому випадку відповідь дорівнює $- 1$ .

Тепер згрупуємо людей за їхнім значенням $c$ . Для кожної такої групи поділимо людей на два типи:

Good — люди, для яких $a_{s} = c$ a_s=c. Така позиція вже сама забезпечує потрібний максимум.
Bad — люди, для яких $a_{s} < c$ a_s<c. Щоб їхній кінцевий рахунок став рівним $c$ , вони повинні відвідати позицію зі значенням $a_{i} = c$ a_i=c.

Розглянемо одну групу з однаковим $c$ . Кожну позицію з Good використаємо як анкор окремого циклу. До цього циклу можна додати не більше ніж $x - 1$ x-1 позицій з Bad.

Таким чином, довжина кожного такого циклу не перевищує $x$ , тому кожна людина в ньому за $x$ кроків обов'язково відвідає анкор зі значенням $c$ . При цьому всі інші позиції людей у цьому циклі мають значення не більше за $c$ , тому кінцевий максимум буде рівно $c$ .

Якщо після використання всіх позицій з Good ще залишилися елементи Bad, потрібно створити для них додаткові цикли. Як анкор для такого циклу використаємо вільну позицію без людини, для якої

a_{i} = c .

a_i=c.

До кожного такого анкора знову додаємо не більше ніж $x - 1$ x-1 позицій з Bad.

Якщо потрібних вільних позицій зі значенням $c$ не вистачає, побудувати перестановку неможливо, тому виводимо $- 1$ .

Також, якщо $x = 1$ x=1 і існує хоча б одна позиція з Bad, відповідь одразу дорівнює $- 1$ , оскільки така людина не встигне перейти на іншу позицію.

Після побудови всіх груп кожен створений набір позицій

v_{1}, v_{2}, \dots, v_{t}

v_1,v_2,\ldots,v_t

замикаємо в цикл:

p_{v_{1}} = v_{2}, p_{v_{2}} = v_{3}, \dots, p_{v_{t}} = v_{1} .

p_{v_1}=v_2,\quad p_{v_2}=v_3,\quad \ldots,\quad p_{v_t}=v_1.

Усі позиції, які не були використані в жодному циклі, робимо нерухомими:

p_{i} = i .

p_i=i.

Таким чином отримуємо коректну перестановку, для якої кінцевий рахунок кожної людини дорівнює заданому значенню $c$ .

Загальна асимптотика — $O (n lo g n)$ O(n\log n) через використання std::map.

Використання пам'яті — $O (n)$ .

a_{j}

a_{s} > c,

a_{s} = c

a_{s} < c

a_{i} = c

x - 1

a_{i} = c .

x - 1

x = 1

v_{1}, v_{2}, \dots, v_{t}

p_{v_{1}} = v_{2}, p_{v_{2}} = v_{3}, \dots, p_{v_{t}} = v_{1} .

p_{i} = i .

O (n lo g n)