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

Задача F. K-sort

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Есмаханда $N$ саннан тұратын $A$ массиві берілген $A_0,A_1,..,A_{N-1}$. Массив $k$-сортталатын деп аталады, егер келесі операцияны бірнеше(мүмкін 0) рет жасап, массивты кемімейтін қылдырып жасауға болса: $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 шығарыңыз.

Система оценки

Есеп 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)