Problem:


Score : 800 points

Problem Statement

You are given a string S consisting of lowercase English letters.
Determine whether we can turn S into a palindrome by repeating the operation of swapping two adjacent characters. If it is possible, find the minimum required number of operations.

Constraints

1 \leq |S| \leq 2 × 10^5

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

If we cannot turn S into a palindrome, print -1. Otherwise, print the minimum required number of operations.

Sample Input 1

eel

Sample Output 1

1

We can turn S into a palindrome by the following operation:

Swap the 2-nd and 3-rd characters. S is now ele.

Sample Input 2

ataatmma

Sample Output 2

4

We can turn S into a palindrome by the following operation:

Swap the 5-th and 6-th characters. S is now ataamtma.

Swap the 4-th and 5-th characters. S is now atamatma.

Swap the 3-rd and 4-th characters. S is now atmaatma.

Swap the 2-nd and 3-rd characters. S is now amtaatma.

Sample Input 3

snuke

Sample Output 3

-1

We cannot turn S into a palindrome.



Sample input:
eel


Sample output:
1

Submission status: Wrong Answer

Solution code:
def main():
    l = list(input())
    N = len(l)
    count=0
    flag = True
    i = 0
    while i <= N>>1:
        if l[i]!=l[N-i-1]:
            if l.count(l[i])%2!=0:
                if flag:
                    temp = l[i]
                    tar_index = N>>1
                    f_index = i
                    count+=tar_index-f_index
                    l[f_index:tar_index] = l[f_index+1:tar_index+1]
                    l[tar_index] = temp
                    flag = False
                else:
                    print(-1)
                    exit()
            else:
                pos = list(reversed(l)).index(l[i],i,N-i-1)
                tar_index = N-1-i
                f_index = N-pos-1
                count += tar_index-f_index
                l[f_index:tar_index] = l[f_index+1:tar_index+1]
                l[tar_index] = l[i]
                i+=1
    print(count)


if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    l = list(input())
    N = len(l)
    count=0
    flag = True
    for i in range(N):
        if l[i]!=l[N-i-1]:
            if l.count(l[i])%2!=0:
                if flag:
                    temp = l[i]
                    tar_index = N>>1
                    f_index = i
                    count+=tar_index-f_index
                    l[f_index:tar_index] = l[f_index+1 :tar_index+1]
                    l[tar_index] = temp
                    flag = False
                else:
                    print(-1)
                    exit()
            else:
                pos = list(reversed(l)).index(l[i],i,N-i-1)
                tar_index = N-1-i
                f_index = N-pos-1
                count += tar_index-f_index
                l[f_index:tar_index] = l[f_index+1:tar_index+1]
                l[tar_index] = l[i]
    print(count)


if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve(s):
    indices = {c: [] for c in ascii_lowercase}
    for i, c in enumerate(s):
        indices[c].append(i)

    n = len(s)
    center = n // 2
    bubbles = [-1] * n
    odd_flag = False
    rights = []
    used = [False] * n
    for c, ids in indices.items():
        cnt = len(ids)
        if cnt & 1:
            if odd_flag:
                return -1
            odd_flag = True
            bubbles[ids[cnt // 2]] = center + 1
            used[center] = True
        for i in range(cnt // 2):
            li, ri = ids[i], ids[-i - 1]
            if li < center:
                bubbles[li] = li + 1
                bubbles[ri] = n - li
                used[n - li - 1] = True
            else:
                rights.append((ri, li))
    rights.sort(reverse=True)
    itr = iter(rights)
    for i in range(n - 1, center, -1):
        if used[i]:
            continue
        ri, li = next(itr)
        bubbles[ri] = i + 1
        bubbles[li] = n - i

    ans = 0
    bit = Bit(n)
    for i, m in enumerate(bubbles):
        ans += i - bit.sum(m)
        bit.add(m, 1)
    return ans


print(solve(input()))

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve(s):
    indices = {c: [] for c in ascii_lowercase}
    for i, c in enumerate(s):
        indices[c].append(i)

    n = len(s)
    center = n // 2
    bubbles = [-1] * n
    odd_flag = False
    rights = []
    used = [False] * (n // 2)
    for c, ids in indices.items():
        cnt = len(ids)
        if cnt & 1:
            if odd_flag:
                return -1
            odd_flag = True
            bubbles[ids[cnt // 2]] = center + 1
        for i in range(cnt // 2):
            li, ri = ids[i], ids[-i - 1]
            if li < center:
                bubbles[li] = li + 1
                bubbles[ri] = n - li
                used[li] = True
            else:
                rights.append((li, ri))
    rights.sort()
    itr = iter(rights)
    for i, flag in enumerate(used):
        if flag:
            continue
        li, ri = next(itr)
        bubbles[li] = i + 1
        bubbles[ri] = n - i

    ans = 0
    bit = Bit(n)
    for i, m in enumerate(bubbles):
        ans += i - bit.sum(m)
        bit.add(m, 1)
    return ans


# return ans


print(solve(input()))

Submission status: Wrong Answer

Solution code:
def main():
    l = list(input())
    N = len(l)
    count=0
    for i in range(N):
        if l[i]!=l[N-i-1]:
            if l.count(l[i])%2!=0 and i!=(N-1)/2:
                print(-1)
                exit()
            else:
                pos = list(reversed(l)).index(l[i],i,N-i)
                tar_index = N-1-i
                f_index = N-pos-1
                count+=abs(tar_index-f_index)
                if tar_index>f_index:
                    l[f_index:tar_index - 1] = l[f_index+1:tar_index]
                else:
                    l[tar_index+1:f_index] = l[tar_index:f_index-1]
                l[tar_index] = l[i]
    print(count)
    
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
S=list(input())
cnt=0
wrg=0
for i in range(len(S)):
    S.count(S[i])
    if S.count(S[i])%2==1:
        wrg+=1
    while S[i]!=S[-(i+1)]:
        S[i],S[i+1]=S[i+1],S[i]
        cnt+=1
if wrg!=1:
    print(-1)
elif cnt!=0:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import Counter


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()

counter = Counter(S)
# 回文にできるかどうかはかんたんに判定できる
if len(S) % 2 == 0:
    ok = True
    for c, cnt in counter.items():
        ok &= cnt % 2 == 0
else:
    odds = 0
    for c, cnt in counter.items():
        odds += cnt % 2 == 1
    ok = odds == 1
if not ok:
    print(-1)
    exit()

# 左右に寄せる。
# 左側か右側かだけで転倒数を数える
counts = [0] * 26
ls = ''
mid = ''
rs = ''
invs = 0
for c in S:
    n = ord(c) - ord('a')
    counts[n] += 1
    if counter[c] & 1:
        if counts[n] <= counter[c] // 2:
            ls += c
            invs += len(rs) + len(mid)
        elif counts[n] == counter[c] // 2 + 1:
            mid += c
            invs += len(rs)
        else:
            rs += c
    else:
        if counts[n] <= counter[c] // 2:
            ls += c
            invs += len(rs) + len(mid)
        else:
            rs += c

rs = rs[::-1]
# 目的の回文への置換回数と同じ回数で ls -> rs に置換できる
l_idx = [[] for _ in range(26)]
for i, c in enumerate(ls):
    n = ord(c) - ord('a')
    l_idx[n].append(i)
counts = [0] * 26
idx = []
for i, c in enumerate(rs):
    n = ord(c) - ord('a')
    idx.append(l_idx[n][counts[n]])
    counts[n] += 1

# idx を昇順にする == ls と同じ並びにするまでの回数
invs2 = 0
bit = BinaryIndexedTree(size=len(ls))
for i in reversed(idx):
    invs2 += bit.sum(i)
    bit.add(i, 1)
ans = invs + invs2
# print(invs, invs2)
# print(ls, rs)
# print(idx)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

S = input()

alpha = defaultdict(int)
N = len(S)
for i in range(N):
	alpha[S[i]] += 1

num = 0
for n in alpha:
	if alpha[n] % 2 == 1:
		num += 1

if num >= 2:
	print(-1)
	exit()

alpha_num = defaultdict(deque)
for i in range(N):
	alpha_num[S[i]].append(i)

loc_list = [-1]*N
num = 0
for i in range(N):
	if len(alpha_num[S[i]]) >= 2:
		x = alpha_num[S[i]].popleft()
		y = alpha_num[S[i]].pop()
		loc_list[x] = num
		loc_list[y] = N - 1 - num
		num += 1
	elif len(alpha_num[S[i]]) == 1:
		x = alpha_num[S[i]].popleft()
		loc_list[x] = N // 2

G = []
ans = 0
for i in range(N):
	x = bisect.bisect(G, loc_list[i])
	bisect.insort(G, loc_list[i])
	ans += i - x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
s = input()
N = len(s)
sc = Counter(s)
odds = sum([1 for x in sc if sc[x] % 2 == 1])
if odds > 1:
    print(-1)
    sys.exit(0)

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size+1)
    def add(self, index, elem):
        index += 1
        while index < len(self.bit):
            self.bit[index] += elem
            index += index & -index
    def get(self, index):
        index += 1
        ret = 0
        while 0 < index:
            ret += self.bit[index]
            index -= index & -index
        return ret



indices = [-1] * N
tb = {c: [None] * sc[c] for c in sc}
lens = {c: 0 for c in sc}
p = 0
for i in range(N):
    c = s[i]
    l = lens[c]
    if 2 * l < sc[c]:
        indices[p] = i
        tb[c][l] = p
        lens[c] += 1
        p += 1
    elif 2 * l == sc[c] + 1:
        indices[N//2] = i
    else:
        indices[N-1-tb[c][sc[c]-l-1]] = i
        lens[c] += 1

ans = 0
bit = BIT(N)
for i in indices:
    bit.add(i, 1)
    ans += bit.get(N-1) - bit.get(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
s = input()
N = len(s)
sc = Counter(s)
odds = sum([1 for x in sc if sc[x] % 2 == 1])
if odds > 1:
    print(-1)
    sys.exit(0)

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size+1)
    def add(self, index, elem):
        index += 1
        while index < len(self.bit):
            self.bit[index] += elem
            index += index & -index
    def get(self, index):
        index += 1
        ret = 0
        while 0 < index:
            ret += self.bit[index]
            index -= index & -index
        return ret



indices = [-1] * N
tb = {}
p = 0
for i in range(N):
    c = s[i]
    if c not in tb:
        indices[p] = i
        tb[c] = [p]
        p += 1
        continue
    l = len(tb[c])
    if 2 * l < sc[c]:
        indices[p] = i
        tb[c].append(p)
        p += 1
    elif 2 * l == sc[c] + 1:
        indices[N//2] = i
    else:
        indices[N-1-tb[c][sc[c]-l-1]] = i
        tb[c].append(p)

ans = 0
bit = BIT(N)
for i in indices:
    bit.add(i, 1)
    ans += bit.get(N-1) - bit.get(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
import math
import numpy as np
import math

class SegmentTree:
    
    def parent(self, k):
        return math.floor((k - 1) / 2)

    def child(self, k, direc):
        """
        0=left, 1=right
        """
        assert direc in (0, 1)
        return k * 2 + 1 + direc
    
    def __init__(self, n_):
        
            # find minimum n>n_ which is a power of 2
            n = 1
            while n < n_:
                n *= 2
            self.n=n
            
            # initialize and update
            self.dat=np.zeros(2 * n  - 1).astype(int)
                
    def update(self, k_, a):
        k = k_ + self.n - 1
        self.dat[k] = a
        while ( k > 0):
            k = self.parent(k)
            self.dat[k] += a
        
    def _query(self, a, b, k, l, r):
        if (r <= a or b <= l):
            return 0
        elif (a <= l and r <= b):
            return self.dat[k]
        else:
            vl = self._query(a, b, self.child(k, 0), l, int( (l+r)/2 ) )
            vr = self._query(a, b, self.child(k, 1), int( (l+r)/2 ), r)
            return vl+vr
        
    def query(self, a, b):
        """
        get minimum in [a, b)
        """
        
        return self._query(a, b, 0, 0, self.n)
      
S=input()
S_lst=list(S)
counter=Counter(S_lst)

margin=len(S)%2
for k, v in counter.items():
    if v%2==1:
        margin -= 1
if not(margin == 0):
    print(-1)
    exit()
    
num_lst=[] # number notation of S
num_ddct=defaultdict(lambda: []) # remember number for palindrome
first_dct={}
thres_dct={}
for k,_ in counter.items():
    first_dct[k]=True
    thres_dct[k]=math.floor(counter[k]/2)

pos=0
for s in S_lst:
    if first_dct[s]: # so far first part
        if len(num_ddct[s]) < thres_dct[s]: # still in first part
            num_lst.append(pos)
            num_ddct[s].append(pos)
            pos += 1
        else: # first time to reach reverse part
            first_dct[s]=False # its not first anymore
            if counter[s]%2==0:  # usual case
                num_lst.append(len(S_lst) - num_ddct[s][-1] - 1)
                num_ddct[s].pop()
            else: # if center
                num_lst.append( int((len(S_lst) - 1) / 2 ) )
    else: # already in second part
        num_lst.append(len(S_lst) - num_ddct[s][-1] - 1)
        num_ddct[s].pop()
        
st=SegmentTree(len(num_lst))
swapCount=0
for i, num in enumerate(num_lst):
    swapCount += i - st.query(0,  num + 1)
    st.update(num, 1)
print(swapCount)

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()

flips = 0
impossible = False
while len(S) > 1:
    ind1 = 0
    ind2 = len(S) - 1
    for i in range(len(S)):
        indi = ind2 - i
        if ind1 == indi:
            if not impossible:
                impossible = True
                break
            else:
                print('-1')
                exit()
        if S[ind1] == S[indi]:
            if indi == ind2:
                S = S[1:-1]
                break
            else:
                S = S[1:indi] + S[indi+1:]
                break
        flips += 1

print(flips)

Submission status: Accepted

Solution code:
from collections import Counter


class fenwick_tree(object):
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def __sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def add(self, p, x):
        """ a[p] += xを行う"""
        assert 0 <= p and p < self.n
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, l, r):
        """a[l] + a[l+1] + .. + a[r-1]を返す"""
        assert 0 <= l and l <= r and r <= self.n
        return self.__sum(r) - self.__sum(l)


def calc_inversion(arr):
    N = len(arr)
    bit = fenwick_tree(N)
    atoi = {a: i for i, a in enumerate(arr)}
    res = 0
    for a in reversed(range(N)):
        i = atoi[a]
        res += bit.sum(0, i)
        bit.add(i, 1)
    return res


def calc_inv(arr):
    N = len(set(arr))
    atoi = {a: i for i, a in enumerate(sorted(set(arr)))}
    bit = fenwick_tree(N)
    res = 0
    for i, a in enumerate(arr):
        res += i - bit.sum(0, atoi[a] + 1)
        bit.add(atoi[a], 1)
    return res


def main():
    S = input()
    N = len(S)
    C = Counter(S)

    odd = 0
    mid = ""
    for k, v in C.items():
        if v & 1:
            odd += 1
            mid = k

    if N % 2 == 0:  # 偶数
        if odd:
            return -1
        half = {k: v // 2 for k, v in C.items()}
        cnt = {k: 0 for k in C.keys()}
        label = []
        left = []
        right = []
        for i, s in enumerate(S):
            if cnt[s] < half[s]:
                label.append(0)
                left.append(s)
            else:
                label.append(1)
                right.append(s)
            cnt[s] += 1
        ans = calc_inv(label)

        pos = {k: [] for k in C.keys()}
        for i, s in enumerate(left):
            pos[s].append(i)
        label = []
        for s in right:
            label.append(pos[s].pop())
        ans += calc_inv(label[::-1])
        return ans

    else:  # 奇数
        if odd != 1:
            return -1
        half = {k: v // 2 for k, v in C.items()}
        cnt = {k: 0 for k in C.keys()}
        label = []
        right = []
        left = []
        seen = 0
        LL = 0  # midの右にあるL
        RR = 0  # midの左にあるR

        for i, s in enumerate(S):
            if s == mid and cnt[s] == half[s]:
                seen = 1
                cnt[s] += 1
                continue
            if cnt[s] < half[s]:
                label.append(0)
                left.append(s)
                if seen:
                    LL += 1
            else:
                label.append(1)
                right.append(s)
                if not seen:
                    RR += 1
            cnt[s] += 1
        ans = calc_inv(label)
        ans += RR + LL

        pos = {k: [] for k in C.keys()}
        for i, s in enumerate(left):
            pos[s].append(i)
        label = []
        for s in right:
            label.append(pos[s].pop())
        ans += calc_inv(label[::-1])
        return ans


print(main())

Submission status: Accepted

Solution code:
"""
まず、奇数個存在する文字種が複数ある場合は、回文にできない。
それ以外の場合は、回文にできる。
次に、操作の最小回数は、回文になった場合の各文字のインデックスを求めておき、BITを使って、入れ替えが必要な回数を求めて置く
"""
from collections import Counter
S = input()
N = len(S)
#各文字の出現回数をカウント
apperance = Counter(S)

#回文を作成できるか判定
flag = False
for k,v in apperance.items():
    if v%2==1:
        if flag:
            print(-1)
            exit()
        else:
            flag = True
            t = k


#place[s] -> 文字sの出現位置
place = {}
for i in range(N):
    s = S[i]
    if s not in place:
        place[s] = []
    place[s].append(i)

#memo[i] -> Sのi文字目の回文上でのインデックス
memo = [-1] *(N)

#回文前半、後半に含まれることになる文字に、回文上でのインデックスを割り当てる。
tmp = 0
tmpApperance = {}
for i in range(N):
    s = S[i]
    if s not in tmpApperance:
        tmpApperance[s] = 1
    else:
        tmpApperance[s] += 1
    if tmpApperance[s] <= apperance[s]//2:
        memo[i] = tmp
        backIdx = place[s][-tmpApperance[s]]
        memo[backIdx] = N-tmp-1
        tmp += 1


#回文の真ん中に含まれることになる文字に、回文上でのインデックスを割り当てる。
if flag:
    idx = N//2
    memo[place[t][len(place[t])//2]] = idx

class BIT:
    def __init__(self,n):
        self.size=n
        self.tree = [0]*(n+1)
    
    def sum(self,i):
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i&-i
        return s
    
    def add(self,i,x):
        while i<=self.size:
            self.tree[i] += x
            i += i&-i
bit = BIT(N)
cnt = 0
for i in range(N):
    m = memo[i]+1
    bit.add(m,1)
    cnt += bit.sum(N)-bit.sum(m)

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter

class BIT:
    def __init__(self,n):
        self.tree = [0]*(n+1)
        self.size = n
    
    def sum(self,i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
        return s

    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i

S = input()
N = len(S)
count = Counter(S)
flag = False
for v in count.values():
    if v%2 == 1:
        if flag:
            print(-1)
            exit()
        else:
            flag = True


"""
文字sのi文字目がどこにあるか、をO(1)で取り出せる辞書が必要
"""
placeAtS = {s:[] for s in list(set(S))}
for i in range(N):
    s = S[i]
    placeAtS[s].append(i)

count2 = {s:0 for s in list(set(S))}

placeAtT = [None]*(N)
tmp = 0
for i in range(N):
    s = S[i]
    count2[s] += 1
    if count2[s] <= count[s]//2:
        placeAtT[i] = tmp
        mirror = placeAtS[s][count[s]-count2[s]]
        placeAtT[mirror] = N - tmp - 1
        tmp += 1

for i in range(N):
    if placeAtT[i] == None:
        placeAtT[i] = tmp

bit = BIT(N)
ans = 0
for i in range(N):
    bit.add(placeAtT[i]+1,1)
    ans += bit.sum(N) - bit.sum(placeAtT[i]+1)

print(ans)

Submission status: Accepted

Solution code:
"""
回文の左半分の文字列たちを操作する。
左半分の各文字に対して、本来あるべき場所(Index)を定義する。
あとは、左半分の文字

"""

from collections import Counter
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):  # 1-index
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  # 1-index
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

S = input()
N = len(S)
count = Counter(S)

#奇数個ある文字が複数存在していないかチェック
flag = False
for v in count.values():
    if v%2 == 1:
        if flag:
            print(-1)
            exit()
        else:
            flag = True

# 各文字が属すべきインデックスを求める
# memo[i] -> S[i]の回文変換後のインデックス(0-indexed)
memo = [None]*(N)
#appearCnt[k] -> 文字kの出現回数
appearCnt = {k:0 for k in count.keys()}

# まず、回文時に左半分に属する文字に関して、インデックスを割り当てる。
tInd = 0
for i in range(N):
    s = S[i]
    if appearCnt[s] <= count[s]//2 - 1:
        appearCnt[s] += 1
        memo[i] = tInd
        tInd += 1

#奇数個ある文字がある場合は、真ん中になる文字に関して、インデックスを割り当てる
if flag:
    for i in range(N):
        s = S[i]
        if count[s]%2 == 1 and memo[i]==None:
            memo[i] = tInd
            break

#回文時に右半分になる文字にインデックスを割り当てる。
#まず、各文字の文字列Sにおける出現回数をまとめる
appearIdx = {k:[] for k in count.keys()}
for i in range(N):
    s = S[i]
    appearIdx[s].append(i)

for v in appearIdx.values():
    for i in range(len(v)//2):
        l = v[i]
        r = v[len(v)-i-1]
        memo[r] = (N-1)-memo[l]
ans = 0
bit = BIT(N)
for i in range(N):
    bit.add(memo[i]+1,1)
    ans += bit.sum(N)-bit.sum(memo[i]+1)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):  # 1-index
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  # 1-index
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    """
    # 使用例
    bit = BinaryIndexedTree(10)     # 要素数を与えてインスタンス化
    bit.add(2, 10)    # a2に10を加える
    bit.add(3, -6)    # a3に-6を加える
    print(bit.sum(6)) # a1～a6の合計を返す
    print(bit.sum(6) - bit.sum(3))  # a4～a6の合計を返す
    """

s = S()
n = len(s)
s_index = defaultdict(list)
for i, x in enumerate(s):
    s_index[x].append(i)

T = [0]*n  # sでi番目の文字は、最終的な回文でT[i]番目の文字となる
flag = False  # 奇数個の文字が前にあったかフラグ(奇数個の文字が2つ以上あってはならない)
AC = []  # 最終的な回文での前半Aと後半Cのペア
for x, index_list in s_index.items():
    count = len(index_list)
    if count % 2 == 1:
        if flag:
            print(-1)
            exit()
        else:
            flag = True
            mid = index_list[count//2]
            T[mid] = n//2  # 回文の中心(B)
    for i in range(count//2):
        a = index_list[i]
        c = index_list[-i-1]
        AC.append((a, c))

AC.sort(key=itemgetter(0))  # 前半(a)の順番でソート
for i, (a, c) in enumerate(AC):
    T[a] = i  # a == i
    T[c] = n - i - 1

BIT = BinaryIndexedTree(n)
inversion = 0
for i, t in enumerate(T):
    i += 1  # 1-indexに変換
    t += 1  # 1-indexに変換
    BIT.add(t, 1)
    inversion += i - BIT.sum(t)
print(inversion)

Submission status: Accepted

Solution code:
from collections import deque
alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

S=input()
N=len(S)

dic={moji:deque([]) for moji in alphabetlist}
for i in range(N):
    dic[S[i]].append(i+1)

left=deque([])
right=deque([])
mid=[]

if N%2==1:
    check=0
    memo=0
    for moji in dic:
        if len(dic[moji])%2==1:
            k=len(dic[moji])
            check+=1
            memo=dic[moji][k//2]
    if check!=1:
        print(-1)
        exit()
    else:
        mid.append(memo)
else:
    check=0
    for moji in dic:
        if len(dic[moji])%2==1:
            print(-1)
            exit()

for i in range(N//2):
    for moji in alphabetlist:
        if len(dic[moji])>=2:
            L=dic[moji][0]
            R=dic[moji][-1]
            for moji2 in alphabetlist:
                if len(dic[moji2])>=2 and dic[moji2][0]<L<R<dic[moji2][-1]:
                    break
            else:
                left.append(L)
                right.appendleft(R)
                dic[moji].popleft()
                dic[moji].pop()
                break

ans=list(left)+mid+list(right)
n=N
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

res=0
for i in range(N):
    res+=i-BIT_query(ans[i])
    BIT_update(ans[i],1)

print(res)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict

class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

s = input()
n = len(s)
c = Counter(s)
flg = 0
if n%2 == 0:
  for i in c.values():
    if i%2:
      print(-1)
      exit()
else:
  for st,i in c.items():
    if i%2 and flg:
      print(-1)
      exit()
    elif i%2:
      flg = 1
ans = 0
fstr = []
lstr = []
dc = defaultdict(int)
ptr = 0
for i in range(n):
  si = s[i]
  dc[si] += 1
  cnt = dc[si]
  if c[si]%2:
    if cnt*2-1 == c[si]:
      ans += i-ptr
      continue
  if cnt <= c[si]//2:
    ans += i-ptr
    ptr += 1
    fstr.append(si)
  else:
    lstr.append(si)
lstr = lstr[::-1]
n //= 2
perm = [0]*n
fdc = defaultdict(list)
ldc = defaultdict(int)
lcnt = 0
for i in range(n):
  fi = fstr[i]
  fdc[fi].append(i+1)
for i in range(n):
  li = lstr[i]
  perm[i] = fdc[li][ldc[li]]
  ldc[li] += 1
sol = Bit(n+2)
for i in range(n):
  p = perm[i]
  ans += sol.sum(n+1)-sol.sum(p)
  sol.add(p,1)
print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)
 

def swap_time(array0, array1):
    n = len(array0)
    memo = {}
    for i in range(n)[::-1]:
        if array0[i] not in memo:
            memo[array0[i]] = []
        memo[array0[i]].append(i)
    res = []
    for val in array1:
        ind = memo[val].pop()
        res.append(ind)
    
    bit = BIT(n)
    ans = 0
    for i in range(n):
        bit.add(res[i], 1)
        ans += bit.get_sum(res[i] + 1, n)
    return ans
  
  

ALPH = "abcdefghijklmnopqrstuvwxyz"
s = input()

cnt_memo = {}
for char in s:
    if char not in cnt_memo:
        cnt_memo[char] = 1
    else:
        cnt_memo[char] += 1

odd = ""
for char in cnt_memo:
    if cnt_memo[char] % 2 == 1:
        if odd:
            print(-1)
            exit()
        else:
            odd = char
            cnt_memo[char] -= 1
            cnt_memo[char] //= 2
    else:
        cnt_memo[char] //= 2

left = []
mid = []
if odd:
    mid = [odd]
right = []
for char in s:
    if odd == char and cnt_memo[char] == 0:
        odd = ""
    elif cnt_memo[char] != 0:
        left.append(char)
        cnt_memo[char] -= 1
    else:
        right.append(char)

ans = 0
ans += swap_time(left + mid + right, list(s))
ans += swap_time(left, right[::-1])
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

s = input()
n = len(s)
a = [-1 for _ in range(n)]
ch = [[] for _ in range(26)]
for i in range(n):
	ch[ord(s[i])-97].append(i)
if sum([len(x)%2 == 1 for x in ch]) > 1:
	print(-1)
	sys.exit()

for i, c in enumerate(ch):
	tmp = i
	l = len(c)
	for j in range(l//2):
		a[c[j]] = tmp
		a[c[l-j-1]] = tmp
		tmp += 26
#print(a)

former, latter = 0, 0
half = False
d = dict()
cur = 0
bubble = []

ans = 0

for x in a:
	if x >= 0:
		if x not in d:
			d[x] = cur
			cur += 1
			former += 1
			ans += latter + half
		else:
			bubble.append(d[x])
			latter += 1
			if n%2 == 1 and not half:
				ans += 1
	else:
		half = True

bit = BIT(n//2+2)
for b in bubble:
	ans += bit.Sum(b+1)
	bit.PointAdd(b+1, 1)

print(ans)