Problem:


Score : 600 points

Problem Statement

There are 2N balls, N white and N black, arranged in a row. The integers from 1 through N are written on the white balls, one on each ball, and they are also written on the black balls, one on each ball.
The integer written on the i-th ball from the left (1 ≤ i ≤ 2N) is a_i, and the color of this ball is represented by a letter c_i.
c_i = W represents the ball is white; c_i = B represents the ball is black.

Takahashi the human wants to achieve the following objective:

For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the white ball with i written on it is to the left of the white ball with j written on it.

For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the black ball with i written on it is to the left of the black ball with j written on it.

In order to achieve this, he can perform the following operation:

Swap two adjacent balls.

Find the minimum number of operations required to achieve the objective.

Constraints

1 ≤ N ≤ 2000

1 ≤ a_i ≤ N

c_i = W or c_i = B.

If i ≠ j, (a_i,c_i) ≠ (a_j,c_j).

Input

Input is given from Standard Input in the following format:

N
c_1 a_1
c_2 a_2
:
c_{2N} a_{2N}

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

3
B 1
W 2
B 3
W 1
W 3
B 2

Sample Output 1

4

The objective can be achieved in four operations, for example, as follows:

Swap the black 3 and white 1.

Swap the white 1 and white 2.

Swap the black 3 and white 3.

Swap the black 3 and black 2.

Sample Input 2

4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1

Sample Output 2

18

Sample Input 3

9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7

Sample Output 3

41



Sample input:
3
B 1
W 2
B 3
W 1
W 3
B 2


Sample output:
4

Submission status: Wrong Answer

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    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
import sys
input = sys.stdin.readline
from copy import deepcopy
def main():
  n = int(input())
  ca = [input().rstrip() for i in range(2*n)]
  dc = [0]*(2*n+1)
  for i in range(2*n):
    if ca[i][0] == "W":
      dc[int(ca[i][2])] = i+1
    else:
      dc[n+int(ca[i][2])] = i+1
  dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
  dp[0][0] = 0
  bit0 = Bit(2*n)
  for i in range(n+1):
    wx = dc[i+1]
    if i:
      bit0.add(dc[i],1)
    if i < n:
      dp[i+1][0] = dp[i][0]+wx-bit0.sum(wx)-1
    bitc = deepcopy(bit0)
    for j in range(n+1):
      if j < n:
        bx = dc[n+j+1]
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+bx-bitc.sum(bx)-1)
        bitc.add(bx,1)
      if i < n:
        dp[i+1][j] = dp[i][j]+wx-bitc.sum(wx)-1
  print(dp[-1][-1])
main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a == "B", int(b)-1) for a, b in ab]
    dct_b = [0]*n
    dct_w = [0]*n
    for i, (a, b) in enumerate(ab):
        if a:
            dct_b[b] = i
        else:
            dct_w[b] = i

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a:
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    dp2 = [10**9]*(n+1)
    dp2[0] = 0
    for i in range(n+1):
        if i < n:
            dp1 = dp2
            dp2 = [10**9]*(n+1)
            t = dct_b[i]
        for j in range(n+1):
            d = dp1[j]
            if j < n:
                t2 = dct_w[j]
                dp1[j+1] = min(dp1[j+1], d+lb[t2][i]+lw[t2][j])
        for j in range(n+1):
            d = dp1[j]
            if i < n:
                dp2[j] = min(dp2[j], d+lb[t][i]+lw[t][j])
    print(dp1[n])


main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]
    dct = {(a, b): i for i, (a, b) in enumerate(ab)}

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a == "B":
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    for i in range(n):
        t = dct[("B", i)]
        for j in range(n+1):
            d = dp[i][j]
            dp[i+1][j] = min(dp[i+1][j], d+lb[t][i]+lw[t][j])
            if j < n:
                t2 = dct[("W", j)]
                dp[i][j+1] = min(dp[i][j+1], d+lb[t2][i]+lw[t2][j])
    for j in range(n+1):
        d = dp[n][j]
        if j < n:
            t2 = dct[("W", j)]
            dp[i][j+1] = min(dp[i][j+1], d+lb[t2][i]+lw[t2][j])
    print(dp[n][n])


main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]
    dct = {(a, b): i for i, (a, b) in enumerate(ab)}

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a == "B":
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    for i in range(n):
        t = dct[("B", i)]
        l = lb[t][i]
        ttt = dp[i]
        tttt = dp[i+1]
        for j in range(n):
            d = ttt[j]
            t2 = dct[("W", j)]
            ttt[j+1] = min(ttt[j+1], d+lb[t2][i]+lw[t2][j])
        for j in range(n+1):
            d = ttt[j]
            tttt[j] = min(tttt[j], d+l+lw[t][j])
    ttt = dp[n]
    for j, d in enumerate(ttt[:-1]):
        t2 = dct[("W", j)]
        ttt[j+1] = min(ttt[j+1], d+lb[t2][n]+lw[t2][j])
    print(ttt[n])


main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    # 一点更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i):
            x, n, bit = i+1, self.n, self.bit
            while x < n+1:
                bit[x] += 1
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]

    f_B = [[0]*(n+1) for _ in [0]*n]  # f_B[i][j] = Bがi個、Wがj個あるときのBを置く手数
    f_W = [[0]*(n+1) for _ in [0]*n]  # f_W[i][j] = Bがi個、Wがj個あるときのWを置く手数
    dp = [10**9]*(n+1)  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0] = 0

    # まずf_Bから出す
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "B":
                f_B[b][i] = bit.sum(n-b-1)+cnt
                bit.add(n-b-1)
            else:
                if b >= i:
                    cnt += 1
    # f_Wも同様
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "W":
                f_W[b][i] = bit.sum(n-b-1)+cnt
                bit.add(n-b-1)
            else:
                if b >= i:
                    cnt += 1
    for i in range(n):
        dp2 = [10**9]*(n+1)
        for j in range(n+1):
            d = dp[j]
            try:
                dp2[j] = min(dp2[j], d+f_B[i][j])
            except:
                pass
            try:
                dp[j+1] = min(dp[j+1], d+f_W[j][i])
            except:
                pass
        dp = dp2
    print(dp[n])


main()

Submission status: Wrong Answer

Solution code:
N=int(input())
dic={"B":[0]*N,"W":[0]*N}
for i in range(2*N):
    c,a=input().split()
    a=int(a)
    dic[c][a-1]=i

dic["B"]=dic["B"][::-1]
dic["W"]=dic["W"][::-1]

ans=[]
for i in range(2*N):
    if dic["B"] and dic["W"]:
        if dic["B"][-1]>dic["W"][-1]:
            ans.append(dic["W"].pop())
        else:
            ans.append(dic["B"].pop())
    elif dic["B"]:
        ans.append(dic["B"].pop())
    else:
        ans.append(dic["W"].pop())

n=2*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
ans=[ans[i]+1 for i in range(2*N)]
for i in range(2*N):
    res+=i-BIT_query(ans[i])
    BIT_update(ans[i],1)

print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
b=[0 for i in range(n+1)]
w=[0 for i in range(n+1)]
l=[]
for i in range(1,2*n+1):
    c,a=input().split()
    a=int(a)
    l.append((a,c))
    if c=="B":
        b[a]=i
    else:
        w[a]=i
ans=0
No=2
while No<n*2:
    No*=2
tree=[0]*(2*No)
for i in range(No-1,No-1+2*n+1):
    tree[i]=1
for i in range(No-2,-1,-1):
    tree[i]=tree[i*2+1]+tree[i*2+2]
def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
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 a,c in l[::-1]:
    if a==1:
        continue
    if c=="B" and b[a]<b[a-1]:
        t=tree[b[a]+No-1]
        add(b[a],-t)
        ans+=query(b[a],b[a-1])*t
        add(b[a-1],t)
        b[a]=b[a-1]
    elif c=="W" and w[a]<w[a-1]:
        t=tree[w[a]+No-1]
        add(w[a],-t)
        ans+=query(w[a],w[a-1])*t
        query(w[a],w[a-1])
        add(w[a-1],t)
        w[a]=w[a-1]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
b=[0 for i in range(n+1)]
w=[0 for i in range(n+1)]
l=[]
for i in range(1,2*n+1):
    c,a=input().split()
    a=int(a)
    l.append((a,c))
    if c=="B":
        b[a]=i
    else:
        w[a]=i
ans=0
No=2
while No<n*2:
    No*=2
tree=[0]*(2*No)
for i in range(No-1,No-1+2*n+1):
    tree[i]=1
for i in range(No-2,-1,-1):
    tree[i]=tree[i*2+1]+tree[i*2+2]
def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
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 a,c in l[::-1]:
    print(ans)
    if a==1:
        continue
    if c=="B" and b[a]<b[a-1]:
        t=tree[b[a]+No-1]
        add(b[a],-t)
        ans+=query(b[a],b[a-1])*t
        add(b[a-1],t)
        b[a]=b[a-1]
    elif c=="W" and w[a]<w[a-1]:
        t=tree[w[a]+No-1]
        add(w[a],-t)
        ans+=query(w[a],w[a-1])*t
        query(w[a],w[a-1])
        add(w[a-1],t)
        w[a]=w[a-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys

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

N = int(sys.stdin.buffer.readline())
CA = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(N * 2)]

# newca = []
# for c, a in CA:
#     a = int(a)
#     newca.append((c, N - a + 1))
# CA = newca[::-1]
# for c, a in CA:
#     print(c, a)

# 逆の色のボールが少ないほうを使う
ans = 0
nexts = {'W': 1, 'B': 1}
for i in range(N * 2):
    j = i
    next_idx = {'W': -1, 'B': -1}
    counts = {'W': 0, 'B': 0}
    while j < 2 * N and (next_idx['W'] == -1 or next_idx['B'] == -1):
        c, a = CA[j]
        a = int(a)
        if nexts[c] == a:
            next_idx[c] = j

        if c == 'W' and next_idx['B'] == -1 or c == 'B' and next_idx['W'] == -1:
            counts[c] += 1
        j += 1
    if counts['W'] < counts['B']:
        j = next_idx['B']
    else:
        j = next_idx['W']

    while j > i:
        CA[j], CA[j - 1] = CA[j - 1], CA[j]
        j -= 1
        ans += 1

    c, a = CA[i]
    a = int(a)
    nexts[c] += 1
print(ans)

# for c, a in CA:
#     print(c, a)

Submission status: Wrong Answer

Solution code:
import os
import sys

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

N = int(sys.stdin.buffer.readline())
CA = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(N * 2)]

# 近い方から使う
ans = 0
nexts = {'W': 1, 'B': 1}
for i in range(N * 2):
    j = i
    c, a = CA[j]
    a = int(a)
    while nexts[c] != a:
        j += 1
        c, a = CA[j]
        a = int(a)
    while j > i:
        CA[j], CA[j - 1] = CA[j - 1], CA[j]
        j -= 1
        ans += 1

    c, a = CA[i]
    a = int(a)
    nexts[c] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(2*n):
    c,a = input().split()
    a = int(a)
    if c == "W":
        a += n
    l.append(a)

pos = [1,n,n+1,2*n]

ans = 0
while l:
    cost = []
    if pos[0] <= pos[1]:
        i = l.index(pos[0])
        cost.append((i,i, 0))
        i = l.index(pos[1])
        cost.append((len(l)-i-1,i, 1))
    if pos[2] <= pos[3]:
        i = l.index(pos[2])
        cost.append((i,i, 2))
        i = l.index(pos[3])
        cost.append((len(l)-i-1,i, 3))
    cost.sort()
    c,i,ind = cost[0]
    ans += c
    l.pop(i)
    if ind%2:
        pos[ind] -= 1
    else:
        pos[ind] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(2*n):
    c,a = input().split()
    a = int(a)
    if c == "W":
        a += n
    l.append(a)

b = 1
w = n+1
ans = 0
while l:
    bi = l.index(b) if b <=n else float("inf")
    wi = l.index(w) if w <= 2*n else float("inf")
    if bi<wi:
        ans += bi
        l.pop(bi)
        b += 1
    else:
        ans += wi
        l.pop(wi)
        w += 1
print(ans)

Submission status: Wrong Answer

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

N = int(input())
black = [None] * (N+1) # 数字 -> 場所
white = [None] * (N+1)
for i in range(1,2*N+1):
    c,a = input().split()
    a = int(a)
    if c == 'W':
        white[a] = i
    else:
        black[a] = i

after = []
b = 1
w = 1
while True:
    if b <= N and w <= N:
        ib = black[b]
        iw = white[w]
        if ib < iw:
            after.append(ib)
            b += 1
        else:
            after.append(iw)
            w += 1
    elif b <= N:
        after.append(black[b])
        b += 1
    elif w <= N:
        after.append(white[w])
        w += 1
    else:
        break

# あとは転倒数を数えて終わり

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

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

tree = [0] * (2*N+10)

answer = 0
for i,x in enumerate(after):
    answer += i - BIT_sum(tree,x)
    BIT_update(tree,x)

print(answer)

Submission status: Wrong Answer

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        '''n = 要素数
        要素の添字iは 0 <= i < n となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, val):
        '''i番目の要素にvalを加算する O(logN)'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i
          
    def _sum(self, i):
        s = 0
        while i > 0: 
            s += self.bit[i] 
            i -= i & -i
        return s
         
    def sum(self, i, j):
        '''区間[i, j)の和を求める O(logN)'''
        return self._sum(j) - self._sum(i)


n = int(input())
info = [list(input().split()) for i in range(2*n)]

memo = {}
for i in range(2*n):
    tmp1, tmp2 = info[i]
    memo[tmp1 + tmp2] = i

#1
bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)    
max_num ={}
max_num["W"] = 0
max_num["B"] = 0

ans1 = 0
for i in range(2*n):
    color, num = info[i]
    if max_num[color] + 1 >= int(num):
        max_num[color] = max(max_num[color], int(num))
        continue
    tmp = 0
    for j in range(max_num[color] + 1, int(num)):
        tmp += bit.sum(memo[color + num], memo[color + str(j)])
        bit.add(memo[color + str(j)], -1)
    max_num[color] = int(num)
    ans1 += tmp

#2
bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)    
min_num ={}
min_num["W"] = n+1
min_num["B"] = n+1

ans2 = 0
for i in range(2*n)[::-1]:
    color, num = info[i]
    if min_num[color] - 1 <= int(num):
        min_num[color] = min(min_num[color], int(num))
        continue
    tmp = 0
    for j in range(int(num) + 1, min_num[color])[::-1]:
        tmp += bit.sum(memo[color + str(j)], memo[color + num])
        bit.add(memo[color + str(j)], -1)
    min_num[color] = int(num)
    ans2 += tmp

#3
bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)    
max_num ={}
min_num ={}
max_num["W"] = 0
min_num["B"] = n+1

ans3 = 0
for i in range(2*n)[::-1]:
    color, num = info[i]
    if color == "B":
        if min_num[color] - 1 <= int(num):
            min_num[color] = min(min_num[color], int(num))
            continue
        tmp = 0
        for j in range(int(num) + 1, min_num[color])[::-1]:
            tmp += bit.sum(memo[color + str(j)], memo[color + num])
            bit.add(memo[color + str(j)], -1)
        min_num[color] = int(num)
        ans3 += tmp
for i in range(2*n):
    color, num = info[i]
    if color == "W":
        if max_num[color] + 1 >= int(num):
            max_num[color] = max(max_num[color], int(num))
            continue
        tmp = 0
        for j in range(max_num[color] + 1, int(num)):
            tmp += bit.sum(memo[color + num], memo[color + str(j)])
            bit.add(memo[color + str(j)], -1)
        max_num[color] = int(num)
        ans3 += tmp

#4
bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)    
max_num ={}
min_num ={}
min_num["W"] = n+1
max_num["B"] = 0

ans4 = 0
for i in range(2*n)[::-1]:
    color, num = info[i]
    if color == "W":
        if min_num[color] - 1 <= int(num):
            min_num[color] = min(min_num[color], int(num))
            continue
        tmp = 0
        for j in range(int(num) + 1, min_num[color])[::-1]:
            tmp += bit.sum(memo[color + str(j)], memo[color + num])
            bit.add(memo[color + str(j)], -1)
        min_num[color] = int(num)
        ans4 += tmp
for i in range(2*n):
    color, num = info[i]
    if color == "B":
        if max_num[color] + 1 >= int(num):
            max_num[color] = max(max_num[color], int(num))
            continue
        tmp = 0
        for j in range(max_num[color] + 1, int(num)):
            tmp += bit.sum(memo[color + num], memo[color + str(j)])
            bit.add(memo[color + str(j)], -1)
        max_num[color] = int(num)
        ans4 += tmp

print(min(ans1, ans2, ans3, ans4))

Submission status: Wrong Answer

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        '''n = 要素数
        要素の添字iは 0 <= i < n となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, val):
        '''i番目の要素にvalを加算する O(logN)'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i
          
    def _sum(self, i):
        s = 0
        while i > 0: 
            s += self.bit[i] 
            i -= i & -i
        return s
         
    def sum(self, i, j):
        '''区間[i, j)の和を求める O(logN)'''
        return self._sum(j) - self._sum(i)


n = int(input())
info = [list(input().split()) for i in range(2*n)]

memo = {}
for i in range(2*n):
    tmp1, tmp2 = info[i]
    memo[tmp1 + tmp2] = i

bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)    
max_num ={}
max_num["W"] = 0
max_num["B"] = 0

ans1 = 0
for i in range(2*n):
    color, num = info[i]
    if max_num[color] + 1 >= int(num):
        max_num[color] = max(max_num[color], int(num))
        continue
    tmp = 0
    for j in range(max_num[color] + 1, int(num)):
        tmp += bit.sum(memo[color + num], memo[color + str(j)])
        bit.add(memo[color + str(j)], -1)
    max_num[color] = int(num)
    ans1 += tmp

bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)    
min_num ={}
min_num["W"] = n+1
min_num["B"] = n+1

ans2 = 0
for i in range(2*n)[::-1]:
    color, num = info[i]
    if min_num[color] - 1 <= int(num):
        min_num[color] = min(min_num[color], int(num))
        continue
    tmp = 0
    for j in range(int(num) + 1, min_num[color])[::-1]:
        tmp += bit.sum(memo[color + str(j)], memo[color + num])
        bit.add(memo[color + str(j)], -1)
    min_num[color] = int(num)
    ans2 += tmp
print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        '''n = 要素数
        要素の添字iは 0 <= i < n となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, val):
        '''i番目の要素にvalを加算する O(logN)'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i
          
    def _sum(self, i):
        s = 0
        while i > 0: 
            s += self.bit[i] 
            i -= i & -i
        return s
         
    def sum(self, i, j):
        '''区間[i, j)の和を求める O(logN)'''
        return self._sum(j) - self._sum(i)


n = int(input())
info = [list(input().split()) for i in range(2*n)]

memo = {}
for i in range(2*n):
    tmp1, tmp2 = info[i]
    memo[tmp1 + tmp2] = i

bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)    
max_num ={}
max_num["W"] = 0
max_num["B"] = 0

ans1 = 0
for i in range(2*n):
    color, num = info[i]
    if max_num[color] + 1 >= int(num):
        max_num[color] = max(max_num[color], int(num))
        continue
    tmp = 0
    for j in range(max_num[color] + 1, int(num)):
        tmp += bit.sum(memo[color + num], memo[color + str(j)])
        bit.add(memo[color + str(j)], -1)
    max_num[color] = int(num)
    ans1 += tmp

bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)    
min_num ={}
min_num["W"] = n+1
min_num["B"] = n+1

ans2 = 0
for i in range(2*n)[::-1]:
    color, num = info[i]
    if min_num[color] - 1 <= int(num):
        max_num[color] = min(max_num[color], int(num))
        continue
    tmp = 0
    for j in range(int(num) + 1, min_num[color])[::-1]:
        tmp += bit.sum(memo[color + str(j)]+1, memo[color + num]+1)
        bit.add(memo[color + str(j)], -1)
    min_num[color] = int(num)
    ans2 += tmp
print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        '''n = 要素数
        要素の添字iは 0 <= i < n となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, val):
        '''i番目の要素にvalを加算する O(logN)'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i
          
    def _sum(self, i):
        s = 0
        while i > 0: 
            s += self.bit[i] 
            i -= i & -i
        return s
         
    def sum(self, i, j):
        '''区間[i, j)の和を求める O(logN)'''
        return self._sum(j) - self._sum(i)


n = int(input())
info = [list(input().split()) for i in range(2*n)]

bit = BIT(2*n)
for i in range(2*n):
    bit.add(i, 1)

memo = {}
for i in range(2*n):
    tmp1, tmp2 = info[i]
    memo[tmp1 + tmp2] = i

max_num ={}
max_num["W"] = 0
max_num["B"] = 0

ans = 0
for i in range(2*n):
    color, num = info[i]
    if max_num[color] + 1 >= int(num):
        max_num[color] = max(max_num[color], int(num))
        continue
    tmp = 0
    for j in range(max_num[color] + 1, int(num)):
        tmp += bit.sum(memo[color + num], memo[color + str(j)])
        bit.add(memo[color + str(j)], -1)
    max_num[color] = int(num)
    ans += tmp
print(ans)

Submission status: Wrong Answer

Solution code:
N =int(input())
ca = [[0 if c=="B" else 1 if c=="W" else (int(c)-1) for c in input().split()] for _ in range(N*2)]

Bi = [N*10]*(N+1)
Wi = [N*10]*(N+1)
BWi = [[N*10]*(N+1) for _ in [0]*2]
for i,row in enumerate(ca):
    c,a = row
    BWi[c][a] = i
ans = 0
BWc = [0,0]
while BWc[0]<N and BWc[1]<N:
    tmp1b = min(BWi[0][BWc[0]+1:]+[N*10])
    tmp1w = min(BWi[1][BWc[1]+1:]+[N*10])
    tc = int(tmp1b > tmp1w)
    tmp1 = min(tmp1b,tmp1w)
    tmp2 = BWi[tc].index(tmp1)
    tmp3 = BWi[tc][BWc[tc]:tmp2]
    tmp0 = min(tmp3) if tmp3 else 0
    if tmp0 > tmp1:
        ans += tmp0 - tmp1
        ca[tmp1:tmp0+1] = [ca[tmp0]] + ca[tmp1:tmp0]
        BWc[tc] -= int(ca[tmp0][1] != BWc[tc])
        for j,row in enumerate(ca[tmp1:tmp0+1],tmp1):
            c,a = row
            BWi[c][a] = j
    BWc[tc] += 1
print(ans)

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


bit_w = None
bit_b = None


def solve(n, w, b):
    bit = Bit(2 * n)

    ans = 0
    nw = nb = 0
    while nw < n and nb < n:
        bc = bit_b.sum(w[nw])
        wc = bit_w.sum(b[nb])
        if bc <= wc:
            ans += w[nw] - bit.sum(w[nw])
            bit_w.add(w[nw], -1)
            bit.add(w[nw], 1)
            nw += 1
        else:
            ans += b[nb] - bit.sum(b[nb])
            bit_b.add(b[nb], -1)
            bit.add(b[nb], 1)
            nb += 1

    if nw == n:
        np = nb
        r = b
    else:
        np = nw
        r = w

    for i in range(np, n):
        for j in range(i + 1, n):
            if r[j] < r[i]:
                ans += 1

    return ans


def main():
    global bit_w, bit_b

    n = input()
    n = int(n)
    w = [0] * n
    b = [0] * n
    bit_w = Bit(2 * n)
    bit_b = Bit(2 * n)
    for i in range(2 * n):
        c, a = input().split()
        a = int(a) - 1
        if c == 'W':
            w[a] = i
            bit_w.add(i, 1)
        else:
            b[a] = i
            bit_b.add(i, 1)


    print(solve(n, w, b))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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

N = int(input())
WP, BP = [2001]*(N+1), [2001]*(N+1)
for i in range(2*N):
    c, a = input().split()
    if c == 'W':
        WP[int(a)] = i+1
    else:
        BP[int(a)] = i+1
Q = [1, 1]
end = [0]*2*N
for i in range(2*N):
    w, b = Q
    if WP[w] < BP[b]:
        end[i] = WP[w]
        if w in [0,N]:
            w = 0
        else:
            w += 1
    else:
        end[i] = BP[b]
        if b in [0,N]:
            b = 0
        else:
            b += 1
    Q = w, b

Tr = BIT(2*N)
ans = N*(2*N-1)
for i in range(2*N):
    ans -= Tr.sum(end[i])
    Tr.add(end[i], 1)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
for i in range(2*n):
  a,b = input().split()
  if a == "B":
    x.append(int(b))
  else:
    x.append(int(b)+n)
a = 1
b = n+1
ans = 0
while True:
  black = x.index(a)
  white = x.index(b)
  if black < white:
    ans += black
    x.pop(black)
    a += 1
    if a== n+1:
      while b < 2*n+1:
        white = x.index(b)
        ans += white
        b +=1
      break   
  else:
    ans += white
    x.pop(white)
    b += 1
    if b == 2*n+1:
      while a < n+1:
        white = x.index(a)
        ans += white
        a +=1
      break
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
c = []
for i in range(2*N):
    a,b=input().split()
    c.append((a, int(b)))
mo = copy.deepcopy(c)
ans = 0
for i in range(2,N+1):
  d = c.index(("B",i))
  e = c.index(("B",i-1))
  if e - d >= 0:
    ans += e - d
    c.pop(e)
    c.insert(d,("B",i-1))
    
for i in range(2,N+1):
  d = c.index(("W",i))
  e = c.index(("W",i-1))
  if e - d >= 0:
    ans += e - d
    c.pop(e)
    c.insert(d,("W",i-1))
    
gyaku = 0
for i in range(2,N+1):
  d = mo.index(("W",i))
  e = mo.index(("W",i-1))
  if e - d >= 0:
    gyaku += e - d
    mo.pop(e)
    mo.insert(d,("W",i-1))
for i in range(2,N+1):
  d = mo.index(("B",i))
  e = mo.index(("B",i-1))
  if e - d >= 0:
    gyaku += e - d
    mo.pop(e)
    mo.insert(d,("B",i-1))
print(min(ans,gyaku))

Submission status: Wrong Answer

Solution code:
from functools import reduce


N = int(input())
row = [reduce(lambda x, y: x+y, input().split()) for _ in range(2*N)]


bn = 1
wn = 1

res = 0


while bn <= N or wn <= N:
    # print(row, bn, wn)
    for i, s in enumerate(row):
        if s == 'B' + str(bn):
            bn += 1
            res += i
            row.pop(i)
            break
        if s == 'W' + str(wn):
            wn += 1
            res += i
            row.pop(i)
            break

# print(row, bn, wn)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
list = []
for _ in range(2 * n):
    list.append(input())

w_num, b_num = 1, 1
result = 0
w = 'W {}'.format(w_num)
b = 'B {}'.format(b_num)
w_index = list.index(w)
b_index = list.index(b)

for _ in range(2 * n):
    if w_index < b_index:
        result += w_index
        w_num += 1
        if w_num > n:
            w_index = 2 * n
            list.remove(w)
            b_index -= 1
            continue
        list.remove(w)
        w = 'W {}'.format(w_num)
        w_index = list.index(w)
        b_index -= 1
    else:
        result += b_index
        b_num += 1
        if b_num > n:
            b_index = 2 * n
            list.remove(b)
            w_index -= 1
            continue
        list.remove(b)
        b = 'B {}'.format(b_num)
        w_index -= 1 
        b_index = list.index(b)
print(result)

Submission status: Wrong Answer

Solution code:
def inpchange(st):
    st2=st.replace("B","0")
    st3=st2.replace("W","1")
    return st3
N=int(input())
c=[0 for i in range(2*N)]
a=[0 for i in range(2*N)]
for i in range(2*N):
    c[i],a[i]=map(int,inpchange(input()).split())
ans=0
while(True):
    k=0
    L=[0 for i in range(2*N)]
    for i in range(2*N-1):
        if L[i]==1:
            continue
        if a[i]>a[i+1]:
            a[i],a[i+1]=a[i+1],a[i]
            c[i],c[i+1]=c[i+1],c[i]
            k+=1
            L[i]=1
            L[i+1]=1
    ans+=k
    if k==0:
        break
print(ans)