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: Accepted

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

# PyPy だと文字列結合がめちゃくちゃ遅いっぽい
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.append(c)
            invs += len(rs) + len(mid)
        elif counts[n] == counter[c] // 2 + 1:
            mid.append(c)
            invs += len(rs)
        else:
            rs.append(c)
    else:
        if counts[n] <= counter[c] // 2:
            ls.append(c)
            invs += len(rs) + len(mid)
        else:
            rs.append(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: Accepted

Solution code:
from collections import Counter
S = input()
N = len(S)
ctr = Counter(S)
if len([1 for v in ctr.values() if v%2]) > 1:
    print(-1)
    exit()

M = None
for k,v in ctr.items():
    if v%2:
        M = k
    ctr[k] //= 2

def ctoi(c):
    return ord(c) - ord('a')
from collections import deque
idxs = [deque() for _ in range(26)]
for i,c in enumerate(S):
    idxs[ctoi(c)].append(i)

A = ''
P = []
i = 0
while len(A) < N//2:
    c = S[i]
    if ctr[c] > 0:
        ctr[c] -= 1
        A += c
        P.append(idxs[ctoi(c)].popleft())
    i += 1
if M:
    P.append(idxs[ctoi(M)].popleft())
for c in A[::-1]:
    P.append(idxs[ctoi(c)].popleft())

def inversion(inds):
    bit = [0] * (N+1)
    def bit_add(x,w):
        while x <= N:
            bit[x] += w
            x += (x & -x)
    def bit_sum(x):
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret
    inv = 0
    for ind in reversed(inds):
        inv += bit_sum(ind + 1)
        bit_add(ind + 1, 1)
    return inv

print(inversion(P))

Submission status: Accepted

Solution code:
"""
どれとペアになるかは最初から確定
位置を決めれば後は転倒数
"""
import sys

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


S = input()

dic = {}

for i,s in enumerate(S):

    if s not in dic:

        dic[s] = []

    dic[s].append(i)

pair = [None] * len(S)
lis = [None] * len(S)

for i in dic:

    for j in range(len(dic[i]) // 2):

        pair[dic[i][j]] = dic[i][-1-j]
        pair[dic[i][-1-j]] = -1

numnone = 0
for i in pair:
    if i == None:
        numnone += 1

if numnone > 1:
    print (-1)
    sys.exit()

nmax = 0
for i,num in enumerate(pair):

    if num == None:
        lis[i] = len(S)//2

    if num != None and num >= 0:
        
        lis[i] = nmax
        lis[num] = len(S)-1-nmax
        nmax += 1

BIT = [0] * (len(S)+1)
ans = 0
lis.reverse()

for i,num in enumerate(lis):

    num += 1
    ans += bitsum(num,BIT)
    bitadd(num,1,BIT)

print (ans)

Submission status: Accepted

Solution code:
from collections import Counter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    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 min_swap_times(s, t):
    if Counter(s) != Counter(t):
        return -1

    n = len(s)
    memo = {}
    for i in range(n):
        if s[i] not in memo:
            memo[s[i]] = [i]
        else:
            memo[s[i]].append(i)
    for i in memo:
        memo[i] = memo[i][::-1]

    array = [0] * n
    for i in range(n):
        array[i] = memo[t[i]][-1]
        del(memo[t[i]][-1])    

    memo = {}
    for i in range(n):
        memo[i] = array[i]
    bit = BIT(n)
    res = 0

    for i in range(n):
        bit.add(memo[i], 1)
        res += bit.get_sum(memo[i] + 1, n)
    return res


import copy

s = input()
n = len(s)
memo = {}
for i in range(n):
    if s[i] not in memo:
        memo[s[i]] = 1
    else:
        memo[s[i]] += 1

odd_cnt = 0
for i in memo:
    odd_cnt += memo[i] % 2
if odd_cnt > 1:
    print(-1)
    exit()

left = []
right = []

memo2 = copy.deepcopy(memo)
ans_cnt = 0
word = ""
for i in range(n):
    if memo2[s[i]]*2 > memo[s[i]] + 1:
        memo2[s[i]] -= 1
        ans_cnt += i - len(left)
        left.append(s[i])
    elif memo2[s[i]]*2 == memo[s[i]] + 1:
        word = s[i]
        memo2[s[i]] -= 1
        right.append(s[i])
    else:
        memo2[s[i]] -= 1
        right.append(s[i])
 
if word != "":
    for i in range(len(right)):
        if right[i] == word:
            ans_cnt += i
            del(right[i])
            break
right = right[::-1]
tmp = min_swap_times(left, right)
if tmp == -1:
    print(-1)
else:
    print(ans_cnt + tmp)

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    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)


import copy

s = input()
n = len(s)
memo = {}
for i in range(n):
    if s[i] not in memo:
        memo[s[i]] = 1
    else:
        memo[s[i]] += 1

odd_cnt = 0
for i in memo:
    odd_cnt += memo[i] % 2
if odd_cnt > 1:
    print(-1)
    exit()

left = []
right = []

memo2 = copy.deepcopy(memo)
ans_cnt = 0
word = ""
for i in range(n):
    if memo2[s[i]]*2 > memo[s[i]] + 1:
        memo2[s[i]] -= 1
        ans_cnt += i - len(left)
        left.append(s[i])
    elif memo2[s[i]]*2 == memo[s[i]] + 1:
        word = s[i]
        memo2[s[i]] -= 1
        right.append(s[i])
    else:
        memo2[s[i]] -= 1
        right.append(s[i])
 
if word != "":
    for i in range(len(right)):
        if right[i] == word:
            ans_cnt += i
            del(right[i])
            break
right = right[::-1]

memo = {}
for i in range(len(right)):
    if right[i] not in memo:
        memo[right[i]] = [i]
    else:
        memo[right[i]].append(i)
for i in memo:
    memo[i] = memo[i][::-1]

for i in range(len(left)):
    tmp = left[i]
    left[i] = memo[tmp][-1]
    del(memo[tmp][-1])

memo = {}
for i in range(len(left)):
    memo[i] = left[i]

bit = BIT(len(left))
for i in range(len(left)):
    bit.add(memo[i], 1)
    ans_cnt += bit.get_sum(memo[i] + 1, len(left))
print(ans_cnt)

Submission status: Accepted

Solution code:
s = input()
cnt = [0] * 26
n = len(s)

for c in s:
    cnt[ord(c) - ord('a')] += 1

odd = -1
for i in range(26):
    if cnt[i] % 2 == 1:
        if odd != -1:
            print(-1)
            exit()
        odd = i

cnt2 = [[] for i in range(26)]
nums = []
left = 0
for i in range(len(s)):
    c = s[i]
    ind = ord(c) - ord('a')
    if len(cnt2[ind]) * 2 + 1 == cnt[ind]:
        cnt2[ind].append((n-1)//2)
        nums.append((n-1)//2)
    elif len(cnt2[ind]) <= (cnt[ind]-1)//2:
        cnt2[ind].append(left)
        nums.append(left)
        left += 1
    else:
        num = n - 1 - cnt2[ind][cnt[ind]-1-len(cnt2[ind])]
        cnt2[ind].append(num)
        nums.append(num)

ans = 0
#print(nums)
bit = [0] * (n+1)
def add(x):
    global bit
    x += 1
    while x <= n:
        bit[x] += 1
        x += x & -x

def sum(x):
    x += 1
    res = 0
    while x:
        res += bit[x]
        x -= x & -x
    return res
for num in nums[::-1]:
    ans += sum(num)
    add(num)

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

# 右端のアルファベット：左端にもっていくとしてよい

S = [None] + [int(x) - ord('a') for x in read().rstrip()]

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

N = len(S) - 1
close = [False] * (N+1)

x_to_I = [deque() for _ in range(26)]
for i,x in enumerate(S[1:],1):
    x_to_I[x].append(i)

counter = [len(I) for I in x_to_I]
odd_cnt = sum(x&1 for x in counter)
if odd_cnt >= 2:
    print(-1)
    exit()

find_center = False
bit = BinaryIndexedTree([0] * (N+1))

answer = 0
for r in range(N,0,-1):
    x = S[r]
    bl = close[r]
    if bl:
        continue
    l = x_to_I[x][0]
    if l == r:
        find_center = True
        continue
    x_to_I[x].pop()
    x_to_I[x].popleft()
    costR = 1 if find_center else 0
    costL = l - 1 - bit.get_sum(l)
    bit.add(l,1)
    bit.add(r,1)
    close[l] = True
    answer += costL + costR

print(answer)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def InversionNumber(lst):
    bit = BitSum(max(lst))
    res = 0
    for i, a in enumerate(lst):
        res += i - bit.sum(a)
        bit.update(a, 1)
    return res

def main():
    s = input()
    n = len(s)
    ord_a = ord("a")
    cnts = [0] * 26
    s_code = []
    flag_odd = False
    for c in s:
        code = ord(c) - ord_a
        s_code.append(code)
        cnts[code] += 1
    odd_code = -1
    for code, cnt in enumerate(cnts):
        if cnt % 2 == 1:
            if flag_odd:
                print(-1)
                exit()
            else:
                odd_code = code
                flag_odd = True
        cnts[code] = cnt // 2
    tois = [[] for _ in range(26)]
    to_sort_idx = []
    new_idx = 1
    for code in s_code:
        if cnts[code] > 0:
            to_sort_idx.append(new_idx)
            tois[code].append(n + 1 - new_idx)
            cnts[code] -= 1
            new_idx += 1
        else:
            if flag_odd and code == odd_code:
                to_sort_idx.append(n // 2 + 1)
                flag_odd = False
            else:
                to_sort_idx.append(tois[code].pop())
    # print(to_sort_idx)
    print(InversionNumber(to_sort_idx))

main()

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)
if len(S) % 2 == 0:
    for x in C.values():
        if x % 2 == 1:
            print(-1)
            exit()
else:
    cnt = 0
    for x in C.values():
        if x % 2 == 1:
            cnt += 1
        if cnt > 1:
            print(-1)
            exit()

cnt1 = 1
cnt2 = (N + 1) // 2 + 1
cnt_char = defaultdict(int)
seq = [0] * N
S1 = []
S2 = []
for i, s in enumerate(S):
    cnt_char[s] += 1
    if C[s] % 2 == 1:
        if cnt_char[s] == C[s] // 2 + 1:
            seq[i] = N // 2 + 1
            continue
    if cnt_char[s] <= C[s] // 2:
        seq[i] = cnt1
        cnt1 += 1
        S1.append(s)
    else:
        seq[i] = cnt2
        cnt2 += 1
        S2.append(s)
S2.reverse()

ans = 0
seq.reverse()
bit1 = Bit(N+1)
for i in range(N):
    ans += bit1.sum(seq[i])
    bit1.add(seq[i], 1)

char2idx = defaultdict(list)
for i, s1 in enumerate(S1):
    char2idx[s1].append(i+1)
for x in char2idx.keys():
    char2idx[x].reverse()

seq_ = []
for i, s2 in enumerate(S2):
    seq_.append(char2idx[s2].pop())

bit2 = Bit(N+1)
seq_.reverse()
for i in range(len(seq_)):
    ans += bit2.sum(seq_[i])
    bit2.add(seq_[i], 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

S = list(input().rstrip())
L = len(S)

# binary indexed tree
bit = [0 for _ in range(L+1)]

# 0からiまでの区間和
# 立っているビットを下から処理
def query_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

# i番目の要素にxを足す
# 覆ってる区間すべてに足す
def add(i, x):
    while i <= L:
        bit[i] += x
        i += i & -i

def main():
    A = {}
    for i, s in enumerate(S):
        if not s in A.keys():
            A[s] = [i]
        else:
            A[s].append(i)
    odd = 0
    dic = {}
    for al, c in A.items():
        dic[al] = 0
        if len(c)%2 != 0:
            odd += 1
    if odd > 1:
        print(-1)
    else:
        make_ind = []
        for s, B in A.items():
            l = len(B)
            if l%2 == 1:
                mid = B[l//2]
            for j, b in enumerate(B):
                if j < l//2:
                    make_ind.append(b)
        make_ind.sort()
        IND = [None]*L
        for i, m in enumerate(make_ind):
            s = S[m]
            IND[m] = i+1
            inv = A[s][len(A[s])-1-dic[s]]
            IND[inv] = L-i
            dic[s] += 1
        if L%2 == 1:
            IND[mid] = L//2+1
        

        ans = 0
        for j, a in enumerate(IND):
            ans += j - query_sum(a)
            add(a, 1)
        
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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)
ans = 0



for i, p in enumerate(loc_list):
	bit.add(p + 1, 1)
	ans += i + 1 - bit.sum(p + 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
S = input()

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

    def update(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i
            
    def query(self, i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= i & -i
            
        return ret

d = defaultdict(list)
for i, v in enumerate(S):
    d[v].append(i + 1)

if sum(len(l) % 2 != 0 for l in d.values()) > 1:
    print(-1)
    exit()

N = len(S)
ctr = []
key_map = [-1] * (N + 1)

for k, v in d.items():
    t = len(v)
    if t % 2  == 1:
        key_map[v[t // 2]] = N // 2 + 1

    for j in range(t // 2):
        ctr.append((v[j], v[-j - 1]))
        
ctr.sort()

for i, (l, r) in enumerate(ctr):
    key_map[l] = i + 1
    key_map[r] = N - i

tree = BIT(N)
ans = 0
for i, v in enumerate(key_map[1:]):
    ans += i - tree.query(v)
    tree.update(v, 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque, defaultdict, Counter

S = input().rstrip()
L = len(S)

c = Counter(S)
if sum((x&1 for x in c.values())) >= 2:
    print(-1)
    exit()

alphabet_to_pos = defaultdict(deque)

for i,x in enumerate(S,1):
    alphabet_to_pos[x].append(i)

after = [None] * len(S)
n = 0
for i,x in enumerate(S,1):
    p = alphabet_to_pos[x]
    if not p:
        continue
    if len(p) == 1:
        p.pop()
        after[L//2] = i
        continue
    p.popleft()
    j = p.pop()
    after[n] = i
    after[L - n - 1] = j
    n += 1

def BIT_update(tree,x):
    while x <= L:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

answer = 0
tree = [0] * (L+1)
for i,x in enumerate(after):
    answer += i - BIT_sum(tree,x)
    BIT_update(tree,x)

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappop, heappush
from string import ascii_lowercase as abc

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)
 
    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


D = [deque() for _ in range(26)]
S = input()
N = len(S)

for i in range(len(S)):
    D[ord(S[i])-97].append(i)

M = [len(D[i])%2 for i in range(26)]
if sum(M) >= 2:
    print(-1)
    exit()

odd = sum(M)

Q = []
for c in range(26):
    if len(D[c]) >= 2:
        l = D[c].popleft()
        r = D[c].pop()
        a = l * 1
        b = N - 1 - r
        if b < a:
            a, b = b, a
        heappush(Q, (a, b, l, r, c))

T = [0]*(N//2)
for i in range(N//2):
    _, _, l, r, c = heappop(Q)
    T[i] = c

    if len(D[c]) >= 2:
        l = D[c].popleft()
        r = D[c].pop()
        a = l * 1
        b = N - 1 - r
        if b < a:
            a, b = b, a
        heappush(Q, (a, b, l, r, c))

L = [[] for i in range(26)]

for i in range(N//2):
    L[T[i]].append(N-1-i)

if odd:
    L[M.index(1)].append(N//2)

for i in range(N//2-1, -1, -1):
    L[T[i]].append(i)

bit = BIT(N)
ans = 0
for i in range(N):
    j = L[ord(S[i]) - 97].pop()
    ans += i - bit.sum(j+1)
    bit.add(j+1, 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

a = list(map(ord, input()))
N = len(a)
La = ord("a")

data = [0]*(N+1)


d = [[] for i in range(26)]
for i , c in enumerate(a):
    d[c-La].append(i)

odd = 0
for v in d:
    if len(v) % 2:
        odd += 1
if not odd <= N%2:
    print(-1)
    exit(0)

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

M = [None]*N
for v in d:
    vl = len(v)
    for i in range(vl):
        if not i <= vl-1-i:
            break
        p = v[i]; q = v[-i-1]
        M[p] = q
        M[q] = p
cnt = 0
B = [0]*N
for i in range(N-1, -1, -1):
    if M[i] <= i:
        B[i] = B[M[i]] = cnt
        cnt += 1

cur = -1
ans = 0
for i in range(N-1, -1, -1):

    if cur < B[i]:
        cur = B[i]
        if M[i] == i:
            ans += N//2 - cur
        else:
            ans += M[i] - get(M[i]+1)
        add(M[i]+1, 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from sys import exit
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)

cnt = 0
SC = Counter(S)
for v in SC.values():
    if v % 2:
        cnt += 1
if cnt > 1:
    print(-1)
    exit()

geta = 10**9+7
T = [None]*N
table = Counter()
idx = dict()
ctr = 0
for i, s in enumerate(S):
    table[s] += 1
    if table[s] <= SC[s]//2: 
        T[i] = ctr
        idx[ord(s)*geta + table[s]] = ctr
        ctr += 1
        continue
    if table[s] > (1+SC[s])//2:
        T[i] = N - 1 - idx[ord(s)*geta+(SC[s] + 1 - table[s])]
        continue
    if SC[s] % 2 and table[s] == (SC[s]+1)//2:
        T[i] = (N-1)//2
        continue
Tr = [None]*N
for i, v in enumerate(T):
    Tr[v] = i
B = BIT(N)
ans = 0
for tr in Tr[::-1]:
    ans += B.sum(tr + 1)
    B.add(tr + 1, 1)
print(ans)

Submission status: Accepted

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])



S = input()
N = len(S)
cnt = [0]*26
for c in S:
    cnt[ord(c)-97] += 1
odd = -1
for i, cn in enumerate(cnt):
    if cn%2 != 0:
        if odd == -1:
            odd = i
        else:
            print(-1)
            exit()
    cnt[i] //= 2
#cnt2 = [0]*26
L = [[] for _ in range(26)]
n = N//2 + 1
B = []
for c in S:
    c_int = ord(c)-97
    if cnt[c_int] == 0:
        if c_int == odd:
            B.append(1)
            odd = -1
        else:
            p = L[c_int].pop()
            B.append(p)
    else:
        L[c_int].append(n)
        B.append(0)
        n-=1
        cnt[c_int] -= 1

bit = Bit(N//2+2)
ans = 0
for i, b in enumerate(B):
    ans += i - bit.sum(b+1)
    bit.add(b, 1)
print(ans)

Submission status: Accepted

Solution code:
import collections


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

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

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

    def __str__(self):
        return str(self.bit)


S = str(input())
N = len(S)
index = collections.defaultdict(list)

for i, c in enumerate(S):
    index[c].append(i)

ctr = N // 2
B = [0] * N
flag = 0
P = []

for c, k in index.items():
    cnt = len(k)
    if cnt % 2:
        if flag == 1:
            print(-1)
            exit()
        flag = 1
        B[k[cnt // 2]] = ctr + 1
    for i in range(cnt // 2):
        l, r = k[i], k[-(i+1)]
        P.append((l, r))

P.sort()

for i, (l, r) in enumerate(P):
    B[l], B[r] = i + 1, N - i

ans = 0
bit = Bit(N)
for i, b in enumerate(B):
    ans += i - bit.sum(b)
    bit.add(b, 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

s=input()
n=len(s)
idx=defaultdict(list)
for i,c in enumerate(s):
    idx[c].append(i)
ctr=n//2
B=[0]*n
flag=False
P=[]
for c,I in idx.items():
    cnt=len(I)
    if cnt%2:
        if flag:
            print(-1)
            exit()
        flag=True
        B[I[cnt//2]]=ctr+1
    for i in range(cnt//2):
        l,r=I[i],I[-i-1]
        P.append((l,r))
P.sort()
for i,(l,r) in enumerate(P):
    B[l],B[r]=i+1,n-i
ans=0
bit=BIT(n)
for i,b in enumerate(B):
    ans+=i-bit.sum(b)
    bit.add(b,1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

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

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

a = ord('a')

def make_index(s):

    index = [[] for _ in range(26)]
    for i, ch in enumerate(s):
        index[ord(ch) - a].append(i)

    return index

def solve(s):

    n = len(s)
    index = make_index(s)

    odd = None
    for code, char_pos in enumerate(index):
        if len(char_pos) % 2 == 1:
            if odd is not None:
                return -1
            odd = code

    bit = Bit(n)

    ans = 0
    cnt = 0
    for i in range(n):
        if bit.sum(i + 1) - bit.sum(i) == 1:
            continue
        code = ord(s[i]) - a
        if code == odd and index[code][-1] == i:
            continue
        cnt += 1
        j = index[code].pop()
        ans += n - cnt - (j - bit.sum(j))
        bit.add(j, 1)
        if n // 2 <= cnt:
            break

    if odd is not None:
        j = index[odd][-1]
        ans += abs(n // 2 - (j - bit.sum(j)))

    return ans


def main():
    s = input()

    print(solve(s))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S=list(input())
N=len(S)
ord_A=ord("a")
alp=[0]*26
odd=-1
for i in range(N):
  m=ord(S[i])-ord_A
  alp[m]+=1
for k in range(26):
  if alp[k]%2==1:
    if odd==-1:
      odd=k
    else:
      print(-1)
      exit()
pos=[[] for i in range(26)]
Sequence=[0]*N
d=0
alp_num=[0]*26
for i in range(N):
  m=ord(S[i])-ord_A
  alp_num[m]+=1
  if 2*alp_num[m]<=alp[m]:
    Sequence[i]=d
    pos[m].append(d)
    d+=1
  elif m==odd and alp_num[m]==alp[m]//2+1:
    Sequence[i]=N//2
  else:
    j=pos[m].pop()
    Sequence[i]=N-1-j

def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
def invnumber(n,A):
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=A[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return n*(n-1)//2-invs

print(invnumber(N,Sequence))