Решение задачи Настя и странный генератор с Codeforces

Без пояснения   Просмотров: 36


Расстроившись после такого отношения Насти, Денис был очень грустным. Ничего не могло развеселить отвергнутого парня. Чтобы хоть как-то развеселиться он решил побродить по подворотням. И, как ни странно, ему улыбнулась удача! Зайдя в первый двор, он встретил странного человека, который чем-то торговал.

Оглядевшись вокруг, Денис подошел к незнакомцу и купил загадочный товар. Им оказался... Генератор случайных перестановок! Именно это мальчик так давно искал!

Придя домой он стал изучать, как работает его генератор и узнал алгоритм. Процесс генерации перестановки состоит из n шагов. На i-м шаге выбирается позиция (индекс) для значения i (1≤i≤n). Позиция для значения i определяется следующим образом:

Для всех j от 1 до n посчитаем rj — минимальный такой индекс, что j≤rj≤n, a позиция rj еще не занята в перестановке. Если таких позиций нет, то будем считать, что значение rj не определено.
Для всех t от 1 до n посчитаем countt — количество таких позиций 1≤j≤n, что значение rj определено и rj=t.
Рассмотрим все еще не занятые позиции перестановки и среди таких рассмотрим позиции, для которых значение в массиве count максимально.
Генератор выбирает одну из таких позиций для значения i. Генератор может выбрать любую позицию.
Рассмотрим работу алгоритма на следующем примере:


Пусть n=5 и алгоритм уже расставил значения 1,2,3 в перестановке. Рассмотрим, как генератор будет выбирать позицию для значения 4:

Значения r будут r=[3,3,3,4,×], где × означает неопределенное значение.
Тогда значения count будут count=[0,0,3,1,0].
Есть только две не занятые позиции в перестановке: 3 и 4. Значение в массиве count для позиции 3 равно 3, для позиции 4 равно 1.
Максимальное значение достигается только для позиции 3, поэтому алгоритм однозначно выберет эту позицию для значения 4.
Довольный своим приобретением Денис пошел домой. Несколько дней без перерыва он генерировал перестановки и решил, что преисполнился в осознании процесса генерации. Он считает, что может придумывать случайные перестановки не хуже генератора.

После этого он выписал первую пришедшую на ум перестановку p1,p2,…,pn и решил узнать, могла ли она получится в результате работы генератора.

К сожалению, эта задача оказалась слишком сложна для него, и он обратился за помощью к вам. Нужно определить, могла ли получиться выписанная перестановка применением описанного алгоритма, если генератор всегда выбирает нужную Денису позицию.

Код

#include <bits/stdc++.h>
using namespace std;

const int M = 2e5 + 100;
int a[M];

void solve() {
	int n; cin >> n;
	int a[n]; for (int &i : a) cin >> i;
	for (int i = 0; i + 1 < n; i++) {
		if (a[i + 1] - a[i] >= 2) {
			cout << "No" << "\n";
			return;
		}
	}
	cout << "Yes" << "\n";
}

int main() {
	int t; cin >> t;
	while (t--) solve();
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться