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:
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 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
        ans = 0
        half = {k: v // 2 for k, v in C.items()}
        memo = {k: [] for k in C.keys()}
        cnt = 0
        bit = fenwick_tree(N)
        right = []
        for i, s in enumerate(S):
            if len(memo[s]) >= half[s]:  # 右
                bit.add(i, 1)
                right.append(s)
            else:  # 左
                memo[s].append(cnt)
                cnt += 1
                ans += bit.sum(0, i)
        arr = []
        for s in right:
            arr.append(memo[s].pop())
        ans += calc_inversion(arr[::-1])
        return ans

    else:  # 奇数
        if odd != 1:
            return -1
        ans = 0
        half = {k: v // 2 for k, v in C.items()}
        memo = {k: [] for k in C.keys()}
        right = []
        cnt = 0
        LL = 0  # midより右にあるLの数
        RR = 0  # midより左にあるRの数
        seen = 0  # midが登場したか

        bit = fenwick_tree(N)
        for i, s in enumerate(S):
            if s == mid and len(memo[s]) == half[s]:
                seen = 1
                memo[s].append(cnt)
            elif len(memo[s]) >= half[s]:  # 右
                bit.add(i, 1)
                right.append(s)
                if not seen:
                    RR += 1
            else:
                memo[s].append(cnt)
                cnt += 1
                ans += bit.sum(0, i)
                if seen:
                    LL += 1
        ans += abs(RR - LL)
        arr = []
        memo[mid].pop()
        for s in right:
            arr.append(memo[s].pop())
        ans += calc_inversion(arr[::-1])
        return ans


print(main())

Submission status: Wrong Answer

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 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
        ans = 0
        half = {k: v // 2 for k, v in C.items()}
        memo = {k: [] for k in C.keys()}
        cnt = 0
        bit = fenwick_tree(N)
        right = []
        for i, s in enumerate(S):
            if len(memo[s]) >= half[s]:  # 右
                bit.add(i, 1)
                right.append(s)
            else:  # 左
                memo[s].append(cnt)
                cnt += 1
                ans += bit.sum(0, i)
        arr = []
        for s in right:
            arr.append(memo[s].pop())
        ans += calc_inversion(arr[::-1])
        return ans

    else:  # 奇数
        if odd != 1:
            return -1
        ans = 0
        half = {k: v // 2 for k, v in C.items()}
        memo = {k: [] for k in C.keys()}
        right = []
        cnt = 0
        LL = 0  # midより右にあるLの数
        RR = 0  # midより左にあるRの数
        seen = 0  # midが登場したか

        bit = fenwick_tree(N)
        for i, s in enumerate(S):
            if s == mid and len(memo[s]) == half[s]:
                seen = 1
                memo[s].append(cnt)
            elif len(memo[s]) >= half[s]:  # 右
                bit.add(i, 1)
                right.append(s)
                if not seen:
                    RR += 1
            else:
                memo[s].append(cnt)
                cnt += 1
                ans += bit.sum(0, i)
                if seen:
                    LL += 1
        ans += max(RR, LL)
        arr = []
        memo[mid].pop()
        for s in right:
            arr.append(memo[s].pop())
        ans += calc_inversion(arr[::-1])
        return ans


print(main())

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

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 += max(0,i-n//2)
      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: Wrong Answer

Solution code:
s=input()
n=len(s)
l=[[] for i in range(26)]
No=2**18
tree=[0 for i in range(2*No)]
for i in range(No-1,No-1+n):
    tree[i]=1
for i in range(No-2,-1,-1):
    tree[i]=tree[i*2+1]+tree[i*2+2]
#kにxを加える(0index)
def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
#lからrまでの和(l,r含む)
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=0
    while L<=R:
        if R&1:
            s+=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s+=tree[L]
        L>>=1;R>>=1
    return s
for i,c in enumerate(s):
    l[ord(c)-97].append(i)
mid=-1
for i in range(26):
    if len(l[i])%2==1:
        if mid!=-1:
            print(-1)
            quit()
        else:
            mid=i
ans=0
i=0
mid=n
while i<=n:
    if tree[i+No-1]==0:
        i+=1
        continue
    t=l[ord(s[i])-97].pop()
    if len(l[ord(s[i])-97])==0:
        mid=t
        add(t,-1)
        i+=1
        continue
    add(t,-1)
    ans+=query(t,n)
    i+=1
ans+=query(mid,n)
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
l=[[] for i in range(26)]
No=2**18
tree=[0]*(2*No)
for i in range(No-1,No-1+n):
    tree[i]=1
for i in range(No-2,-1,-1):
    tree[i]=tree[i*2+1]+tree[i*2+2]
#kにxを加える(0index)
def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
#lからrまでの和(l,r含む)
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=0
    while L<=R:
        if R&1:
            s+=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s+=tree[L]
        L>>=1;R>>=1
    return s
for i,c in enumerate(s):
    l[ord(c)-97].append(i)
mid=-1
for i in range(26):
    if len(l[i])%2==1:
        if mid!=-1:
            print(-1)
            quit()
        else:
            mid=i
ans=0
i=0
mid=n
while i<=n:
    if tree[i+No-1]==0:
        i+=1
        continue
    t=l[ord(s[i])-97].pop()
    if len(l[ord(s[i])-97])==0:
        mid=t
        add(t,-1)
        i+=1
        continue
    add(t,-1)
    ans+=query(t,n)
    i+=1
ans+=query(mid,n)
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
l=[[] for i in range(26)]
No=2**18
tree=[0]*(2*No)
for i in range(No-1,No-1+n):
    tree[i]=1
for i in range(No-2,-1,-1):
    tree[i]=tree[i*2+1]+tree[i*2+2]
#kにxを加える(0index)
def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
#lからrまでの和(l,r含む)
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=0
    while L<=R:
        if R&1:
            s+=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s+=tree[L]
        L>>=1;R>>=1
    return s
for i,c in enumerate(s):
    l[ord(c)-97].append(i)
mid=-1
for i in range(26):
    if len(l[i])%2==1:
        if mid!=-1:
            print(-1)
            quit()
        else:
            mid=i
if mid>-1 and l[mid][len(l[mid])//2]<n//2:
    s=s[::-1]
    l=[[] for i in range(26)]
    for i,c in enumerate(s):
        l[ord(c)-97].append(i)
ans=0
i=0
while i<=n:
    if tree[i+No-1]==0:
        i+=1
        continue
    t=l[ord(s[i])-97].pop()
    add(t,-1)
    ans+=query(t,n)
    i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
X = [0] * 26
for s in S:
    X[ord(s)-97] += 1

if sum([x&1 for x in X]) > 1:
    print(-1)
else:
    D = {}
    Y = [0] * 26
    ans = 0
    p = 0
    for i in range(N):
        s = ord(S[i]) - 97
        Y[s] += 1
        n = (X[s] - Y[s] + 1) * 26 + s
        if n in D:
            ans += abs(N - 1 - D[n] - i)
        else:
            if X[s] == Y[s] * 2 - 1:
                D[Y[s] * 26 + s] = N//2
                ans += abs(i - N//2)
            else:
                D[Y[s] * 26 + s] = p
                ans += abs(p-i)
                p += 1
    print(ans//2)

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
X = [0] * 26
for s in S:
    X[ord(s)-97] += 1

if sum([x&1 for x in X]) > 1:
    print(-1)
else:
    D = {}
    Y = [0] * 26
    ans = 0
    p = 0
    for i in range(N):
        s = ord(S[i]) - 97
        Y[s] += 1
        n = (X[s] - Y[s] + 1) * 26 + s
        if n in D:
            ans += abs(N - 1 - D[n] - i)
        else:
            D[Y[s] * 26 + s] = p
            ans += abs(p-i)
            p += 1
    print(ans//2)

Submission status: Wrong Answer

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: Wrong Answer

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)
            else:
                to_sort_idx.append(tois[code].pop())
    # print(to_sort_idx)
    print(InversionNumber(to_sort_idx))

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

data = [0]*(N+1)


d = defaultdict(list)
for i , c in enumerate(a):
    d[c-La].append(i)
print(d)
odd = 0
for v in d:
    if len(d[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:
    v = d[v]
    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: Wrong Answer

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
print(B)

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: Wrong Answer

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

s = input()
n = len(s)
cnt = [[] for _ in range(26)]
for i in range(n):
	cnt[ord(s[i])-97].append(i)

odd = 0
for c in cnt:
	if len(c)%2 == 1:
		odd += 1

if odd - (n%2) > 0:
	print(-1)
	sys.exit()

res = 0
for i in range(26):
	m = len(cnt[i])
	for j in range(m//2):
		res += min(abs(n-1-cnt[i][j] - cnt[i][m-1-j]), abs(n-1-cnt[i][m-1-j] - cnt[i][j]))
	if m%2 == 1:
		res += abs(cnt[i][m//2] - n//2)

print(res//2)

Submission status: Wrong Answer

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

    if odd is not None:
        if index[odd][len(index[odd]) // 2] < n // 2:
            s = ''.join(list(reversed(s)))
            index = make_index(s)

    bit = Bit(n)

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

    return ans


def main():
    s = input()

    print(solve(s))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    if odd is not None:
        if index[odd][len(index[odd]) // 2] < n // 2:
            s = ''.join(list(reversed(s)))
            index = make_index(s)

    bit = Bit(n)

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

    return ans


def main():
    s = input()

    print(solve(s))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
#from collections import defaultdict
S=input()
N = len(S)
L = 26
a = ord('a')
d = [[] for i in range(L)]
for i in range(N):
    s=ord(S[i])-a
    d[s].append(i)
flag=0
for i in range(L):
    if len(d[i])%2==1:
        flag+=1
if flag>1:
    print(-1)
    sys.exit()
Suc=[-1]*N
pairs=[]
for i in range(L):
    T=len(d[i])
    for s in range((T//2)):
        li,ri=d[i][s],d[i][-s-1]
        pairs.append((li,ri))
    if T%2==1:
        Suc[d[i][T//2]]=(N//2)+1
pairs.sort()
for i, (li,ri) in enumerate(pairs):
    Suc[li]=i+1
    Suc[ri]=N-i
Tree=BIT(N+3)
ans=0
for i in range(N):
    Tree.add(Suc[i],1)
    ans+=Tree.search(i+1)
print((N*(N+1))//2-ans)

Submission status: Wrong Answer

Solution code:
import sys
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
#from collections import defaultdict
S=input()
N = len(S)
L = 26
a = ord('a')
d = [[] for i in range(L)]
for i in range(N):
    s=ord(S[i])-a
    d[s].append(i)
flag=0
for i in range(L):
    if len(d[i])%2==1:
        flag+=1
if flag>1:
    print(-1)
    sys.exit()
Suc=[-1]*N
pairs=[]
for i in range(L):
    T=len(d[i])
    for s in range((T//2)):
        li,ri=d[i][s],d[i][T-s-1]
        pairs.append((li,ri))
    if T%2==1:
        Suc[d[i][T//2]]=(N//2)+1
pairs.sort()
for i, (li,ri) in enumerate(pairs):
    Suc[li]=i+1
    Suc[ri]=N-i
Tree=BIT(N+3)
ans=0
for i in range(N):
    Tree.add(Suc[i],1)
    ans=ans+i+1-Tree.search(i+1)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq,string

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    s = f.read_str()
    n = len(s)
    d = [collections.deque() for _ in xrange(26)]
    p = [-1] * n

    for i, si in enumerate(s):
        d[ord(si)-ord('a')].append(i+1)

    odd = None
    for i in xrange(26):
        if len(d[i])%2 == 1:
            if odd is not None: return -1
            odd = i

    if odd is not None: p[n/2] = d[odd][len(d[odd])/2]

    for i in xrange(1,n/2+1):
        mi = float('inf')
        si = None
        for j in xrange(26):
            if len(d[j]) < 2: continue
            diff = abs(d[j][0]-i) + abs(d[j][-1]-(n-i))
            if diff < mi:
                mi = diff
                si = j

        p[i-1] = d[si].popleft()
        p[n-i] = d[si].pop()

    return count_inversion(p)


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in xrange(size + 1)]
        self.size = size

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

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


def count_inversion(a):
    n = len(a)
    ans = 0
    bit = BinaryIndexedTree(n)
    for i in xrange(n):
        ans += i - bit.sum(a[i])
        bit.add(a[i], 1)
    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
from collections import Counter

text = input()
count = Counter()

def change_count(text):
    N = len(text)
    origin = 0
    print(text)
    if N <= 2:
        return 0
    elif text[0] == text[N-1]:
        return change_count(text[1:N-1])
    else:
        if count[0] % 2 == 1:
            origin = N-1
        start = 1
        while text[origin] != text[start]:
            start = start + 1
        end = N-2
        while text[origin] != text[end]:
            end = end - 1

        if origin == 0:
            if start >= end :
                return (N-1)-start + change_count(text[1:start]+text[start+1:])
            else:
                return (N-1)-end + change_count(text[1:end]+text[end+1:])
        else:
            if start < end :
                return start + change_count(text[0:start]+text[start+1:N-1])
            else:
                return end + change_count(text[0:end]+text[end+1:N-1])


for c in text:
    count[c] = count[c] + 1

odd = 0
for k, c in count.items():
    if c % 2 == 1:
        odd = odd + 1

if odd >= 2:
    print(-1)
else:
    print(change_count(text))

Submission status: Wrong Answer

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

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()
print(-1)

Submission status: Wrong Answer

Solution code:
# test -1 cases
from collections import Counter as C
s = dict(C(raw_input()))
v = s.values()
if max(v) - min(v) + 1 == len(s):
    print 0
else:
    print -1

Submission status: Wrong Answer

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
                S = S[1:]
                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: 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
        else:
            i+=1
    print(count)


if __name__=="__main__":
    main()