Областная олимпиада по информатике 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 )

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

import copy

n,q=map(int,input().split())

a=[int(x) for x in input().split()]

c=[]

for i in range(q):

b=copy.deepcopy(a)

k=int(input())

for i in range(0,n):

m=(i+k)%n

b[i],b[m]=b[m],b[i]

if b==sorted(a):

x=1

break

else:

x=0

c.append(x)

for i in c:

print(i)