Problem:

Bozosort

    　

  Bozosort, as well as Bogosort, is a very inefficient sort algorithm. It is a random number-based algorithm that sorts sequence elements following the steps as below:

 Randomly select two elements and swap them.

 Verify if all the elements are sorted in increasing order.

 Finish if sorted, else return to 1.

  To analyze Bozosort, you have decided to simulate the process using several predetermined pairs of elements.

  You are given several commands to swap two elements. Make a program to evaluate how many times you have to run the command before the sequence is aligned in increasing order.

Input

The input is given in the following format.

$N$
$a_1$ $a_2$ ... $a_N$
$Q$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_Q$ $y_Q$

The first line provides the number of sequence elements $N$ ($2 \leq N \leq 300,000$). The second line provides an array of integers $a_i$ ($1 \leq a_i \leq 10^9$) that constitutes the sequence. Each of the subsequent $Q$ lines provides a pair of integers $x_i,y_i$ ($1 \leq x_i,y_i \leq N$) that represent the $i$-th command, which swaps the two elements indicated by $x_i$ and $y_i$ ($x_i \ne y_i$).

Output

  If neat alignment in increasing order is realized the first time after execution of multiple commands, output at what time it was. Output 0 if the initial sequence is aligned in increasing order, and -1 if exhaustive execution still failed to attain the goal.

Sample Input 1

6
9 7 5 6 3 1
3
1 6
2 5
3 4

Sample Output 1

2

Sample Input 2

4
4 3 2 1
2
1 2
3 4

Sample Output 2

-1

Sample Input 3

5
1 1 1 2 2
1
1 2

Sample Input 3

0



Sample input:
6
9 7 5 6 3 1
3
1 6
2 5
3 4


Sample output:
2

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
asort=a[:]
asort.sort()
q=int(input())
count=0
for i in range(q):
    if a==asort:
        print(count)
        break
    x,y=list(map(int,input().split()))
    a[x-1],a[y-1]=a[y-1],a[x-1]
    count+=1
    if count==q:print("-1")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
asort=a[:]
asort.sort()
q=int(input())
count=0
for i in range(q):
    if a==asort:
        print(count)
        break
    x,y=list(map(int,input().split()))
    a[x-1],a[y-1]=a[y-1],a[x-1]
    count+=1
if a==asort:print(count)
elif count==q:print("-1")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
asort=a[:]
asort.sort()
q=int(input())
count=0
for i in range(q):
    if a==asort:
        print(count)
        break
    x,y=list(map(int,input().split()))
    a[x-1],a[y-1]=a[y-1],a[x-1]
    count+=1
if count==q:
    if a==asort:print(count)
    else:print("-1")

Submission status: Accepted

Solution code:

def solve():
    N = int(input())
    a = [int(i) for i in input().split()]
    Q = int(input())
    sort_a = sorted(a)
    judge = 0
    for i in range(N):
        if a[i] != sort_a[i]:
            judge += 1
    if judge == 0:
        print(0)
    else:
        for i in range(Q):
            x, y = map(int, input().split())
            tmp = a[x - 1]
            a[x - 1] = a[y - 1]
            a[y - 1] = tmp
            if a[x - 1] == sort_a[x - 1] and a[y - 1] != sort_a[x - 1]:
                judge -= 1
            if a[x - 1] != sort_a[x - 1] and a[y - 1] == sort_a[x - 1]:
                judge += 1
            if a[y - 1] == sort_a[y - 1] and a[x - 1] != sort_a[y - 1]:
                judge -= 1
            if a[y - 1] != sort_a[y - 1] and a[x - 1] == sort_a[y - 1]:
                judge += 1
            if judge == 0:
                print(i + 1)
                break
        else:
            print(-1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N = int(readline())
*A, = map(int, readline().split())
C = A[:]
C.sort()

MOD = 4253024257
base = 3
B = [0]*N
v = 1
P = Q = 0
for i in range(N):
    B[i] = v
    P += v * A[i]
    Q += v * C[i]
    v = v * base % MOD
if P == Q:
    print(0)
    exit(0)

for i in range(int(readline())):
    x, y = map(int, readline().split()); x -= 1; y -= 1
    p = A[x]; q = A[y]; r = B[y] - B[x]
    P += r * p - r * q
    if P == Q:
        print(i+1)
        break
    A[x], A[y] = q, p
else:
    print(-1)

Submission status: Accepted

Solution code:
INF = 2000000000
diff = 0

def update(i, v):
  global diff
  d1 = 0
  d2 = 0
  if A[i-1] > A[i]: d1 += 1
  if A[i] > A[i+1]: d1 += 1
  A[i] = v
  if A[i-1] > A[i]: d2 += 1
  if A[i] > A[i+1]: d2 += 1
  diff += (d2 - d1)

def solve():
    global diff
    for i in range(1, N+1):
        if  A[i-1] > A[i]: diff += 1

    if diff == 0: return 0
    q = int(input())
    for i in range(1, q+1):
        a,b = map(int, input().split())
        v1 = A[a]
        v2 = A[b]
        update(a, v2)
        update(b, v1)
        if diff == 0:  return i

    return -1

N = int(input())
A = list(map(int, input().split()))
A.insert(0, -INF)
A.append(INF)
print(solve())

Submission status: Accepted

Solution code:
n = int(input())
a_lst = list(map(int, input().split()))
q = int(input())
query = [tuple(map(int, input().split())) for _ in range(q)]
comp = sorted(a_lst)
diff = sum([a_lst[i] != comp[i] for i in range(n)])
if diff == 0:
  print(0)
else:
  for i in range(q):
    x, y = query[i]
    x -= 1
    y -= 1
    diff -= (a_lst[x] == comp[y]) + (a_lst[y] == comp[x]) - (a_lst[x] == comp[x]) - (a_lst[y] == comp[y])
    if diff == 0:
      print(i + 1)
      break
    a_lst[y], a_lst[x] = a_lst[x], a_lst[y]
  else:
    print(-1)