Problem: Snuke got an integer sequence of length N from his mother, as a birthday present. The i-th (1 ≦ i ≦ N) element of the sequence is a_i. The elements are pairwise distinct. He is sorting this sequence in increasing order. With supernatural power, he can perform the following two operations on the sequence in any order:    * Operation 1: choose 2 consecutive elements, then reverse the order of those elements.   * Operation 2: choose 3 consecutive elements, then reverse the order of those elements.  Snuke likes Operation 2, but not Operation 1. Find the minimum number of Operation 1 that he has to perform in order to sort the sequence in increasing order.

Submission attempts (in order):
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* 
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)


def main():
    n,*a=map(int,open(0).read().split())
#    print(a)
    while 1:
        flag=0
        for i in range(n-2):
            if a[i]>a[i+2]:
                a[i],a[i+2]=a[i+2],a[i]
                flag=1
        if not flag:
            break
#    print(a)
    ans=0
    while 1:
        flag=0
        for i in range(n-1):
            if a[i]>a[i+1]:
                a[i],a[i+1]=a[i+1],a[i]
                flag=1
                ans+=1
        if not flag:
            break
#    print(a)
    print(ans)
    
if __name__ == '__main__':
    main()

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* 
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)


def main():
    n,*a=map(int,open(0).read().split())
    b=sorted(a[::2])
    c=sorted(a[1::2])
#    print(b,c)
    ans=0
    for i in range(n//2):
        ans+=abs(i-bisect_left(c,b[i]))

    if len(b)!=n//2:
        ans+=n//2-bisect_left(c,b[-1])
    print(ans)
if __name__ == '__main__':
    main()

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* 
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)


def main():
    n,*a=map(int,open(0).read().split())
    b=sorted(a[::2])
    c=sorted(a[1::2])
#    print(b,c)
    ans=0
    for i in range(n//2):
        ans+=abs(i-bisect_left(c,b[i]))

    if len(b)!=n//2:
        ans+=abs(n//2-bisect_left(c,b[-1]))
    print(ans)
if __name__ == '__main__':
    main()

n,*a=map(int,open(0).read().split());print(len(set(a[::2])^set(sorted(a)[::2]))//2)

Verdicts: Time Limit Exceeded

Wrong Answer

Wrong Answer

Accepted