Областная олимпиада по информатике 2020 год, 9-11 классы


Задача F. K-sort

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Есмахана есть массив $A$ состоящий из $N$ целых чисел $A_0,A_1,..,A_{N-1}$. Массив называется $k$-сортируемым, если массив можно отсортировать по неубыванию c помощью нескольких(возможно ноль) таких операции: выбрать индекс $i(0 <= i < N)$ и поменять местами $i$-й и $((i + k)$ mod $N$)-й элементы массива. Операция $a$ mod $b$ означает остаток $a$ при делении на $b$. Например, $7$ mod $3$ = 1, $8$ mod $4$ = 0, $5$ mod $11$ = 5. Массив считается отсортированным по неубыванию, если каждый элемент(кроме первого) не меньше чем предыдущий элемент. Есть $Q$ запросов, каждый запрос состоит из одного целого числа $k$. Для каждого запроса нужно определить, является ли массив $A$ $k$-сортируемым.
Формат входного файла
В первой строке находятся два целых числа $N,Q(1 <= N,Q <= 300000)$. Во второй строке находятся $N$ целых числа $A_0,A_1, ..., A_{N - 1}(1 <= A_i <= 10^9)$. В следующих $q$ строках находятся по одному целому числу $k_i(1 <= k_i <= N)$.
Формат выходного файла
В $q$ строках выведите по одному целому числу — в $i$-й строке выведите $1$, если массив $A$ является $k_i$-сортируемым, иначе выведите 0.
Система оценки
Это задача состоит из 5 подзадач и 25 тестов, каждый тест оценивается в 4 балла. В подзадачах выполняются следующие дополнительные ограничения:
  1. $1 <= N,Q <= 100$. Тесты 1 -- 4
  2. $1 <= N <= 100000, Q = 1$, $k_1 = N$. Тесты 5 -- 7
  3. $1 <= N,Q <= 2000$. Тесты 8 -- 11
  4. $1 <= N,Q <= 50000$. Тесты 12 -- 15
  5. $1 <= N,Q <= 300000$. Тесты 16 -- 25
Пример:
Вход
4 4
3 2 2 4
1
3
2
4
Ответ
1
1
1
0
Замечание
Изначально $A={3,2,2,4}$, т.е $A_0 = 3, A_1 = 2, A_2 = 2, A_3 = 4$. Массив $3$-сортируемый, потому что с помощью следующих операции можно отсортировать:
  1. Выберем $i = 1$, тогда $(i + 3)$ mod $N = (1 + 3)$ mod $4 = 0$. Т.е поменяем местами $A_1$ и $A_0$. Получиться $A = {2,3,2,4}$.
  2. Выберем $i = 2$, тогда $(i + 3)$ mod $N = (2 + 3)$ mod $4 = 1$. Т.е поменяем местами $A_2$ и $A_1$. Получиться $A = {2,2,3,4}$.
( Temirlan Satylkhanov )
посмотреть в олимпиаде

Комментарий/решение: