Problem:


Score : 700 points

Problem Statement

There is an H \times W grid (H vertical, W horizontal), where each square contains a lowercase English letter.
Specifically, the letter in the square at the i-th row and j-th column is equal to the j-th character in the string S_i.

Snuke can apply the following operation to this grid any number of times:

Choose two different rows and swap them. Or, choose two different columns and swap them.

Snuke wants this grid to be symmetric.
That is, for any 1 \leq i \leq H and 1 \leq j \leq W, the letter in the square at the i-th row and j-th column and the letter in the square at the (H + 1 - i)-th row and (W + 1 - j)-th column should be equal.

Determine if Snuke can achieve this objective.

Constraints

1 \leq H \leq 12

1 \leq W \leq 12

|S_i| = W

S_i consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
:
S_H

Output

If Snuke can make the grid symmetric, print YES; if he cannot, print NO.

Sample Input 1

2 3
arc
rac

Sample Output 1

YES

If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:

Sample Input 2

3 7
atcoder
regular
contest

Sample Output 2

NO

Sample Input 3

12 12
bimonigaloaf
faurwlkbleht
dexwimqxzxbb
lxdgyoifcxid
ydxiliocfdgx
nfoabgilamoi
ibxbdqmzxxwe
pqirylfrcrnf
wtehfkllbura
yfrnpflcrirq
wvcclwgiubrk
lkbrwgwuiccv

Sample Output 3

YES



Sample input:
2 3
arc
rac


Sample output:
YES

Submission status: Accepted

Solution code:
def _3():
    from collections import defaultdict

    def can_pair(s1, s2):
        l = []
        for c1, c2 in zip(s1, s2):
            c = sorted([c1, c2])
            if c in l:
                l.remove(c)
            else:
                l.append(c)

        if len(s1) % 2 == 0:
            return len(l) == 0
        else:
            return len(l) == 1 and l[0][0] == l[0][1]

    def pair_graph(s1, s2):
        N = len(s1)
        G = np.zeros([N, N])
        for i in range(N):
            for j in range(i+1, N):
                if s1[i] == s2[j] and s1[j] == s2[i]:
                    G[i, j] = 1
                    G[j, i] = 1
        return G

    import numpy as np
    H, W = list(map(int, input().split(' ')))
    S = []
    d = defaultdict(list)

    for h in range(H):
        s = input()
        S.append(s)
        d[''.join(sorted(S))].append(h)

    already_paired = np.zeros(H)

    Gs = []

    for i in range(H):
        if already_paired[i]:
            continue

        for j in range(i+1, H):
            if already_paired[j]:
                continue

            if can_pair(S[i], S[j]):
                already_paired[i] = 1
                already_paired[j] = 1
                G = pair_graph(S[i], S[j])
                Gs.append(G)
                break

    if already_paired.sum() < H - 1:
        print('NO')
        exit()

    elif already_paired.sum() == H - 1:
        for i in range(H):
            if already_paired[i] == 0:
                G = pair_graph(S[i], S[i])
                Gs.append(G)
                break

    G = np.array(Gs).sum(axis=0) // len(Gs)

    def is_perfect_matching(G):
        N = len(G)
        if N == 1:
            return True

        for i in range(N):
            for j in range(i+1, N):
                if G[i, j] == 1:
                    l = list(range(N))
                    l.remove(i)
                    l.remove(j)
                    if len(l) == 0:
                        return True
                    if is_perfect_matching(G[l][:, l]):
                        return True
        return False

    if is_perfect_matching(G):
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    _3()

Submission status: Accepted

Solution code:
def _3():
    from collections import defaultdict

    def can_pair(s1, s2):
        l = []
        for c1, c2 in zip(s1, s2):
            c = sorted([c1, c2])
            if c in l:
                l.remove(c)
            else:
                l.append(c)

        if len(s1) % 2 == 0:
            return len(l) == 0
        else:
            if len(l) == 1:
                if l[0][0] == l[0][1]:
                    return True
            return False

    def pair_graph(s1, s2):
        N = len(s1)
        G = np.zeros([N, N])
        for i in range(N):
            for j in range(i+1, N):
                if s1[i] == s2[j] and s1[j] == s2[i]:
                    G[i, j] = 1
                    G[j, i] = 1
        return G

    import numpy as np
    H, W = list(map(int, input().split(' ')))
    S = []
    d = defaultdict(list)

    for h in range(H):
        s = input()
        S.append(s)
        d[''.join(sorted(S))].append(h)

    already_paired = np.zeros(H)

    Gs = []

    for i in range(H):
        if already_paired[i]:
            continue

        for j in range(i+1, H):
            if already_paired[j]:
                continue

            if can_pair(S[i], S[j]):
                already_paired[i] = 1
                already_paired[j] = 1
                G = pair_graph(S[i], S[j])
                Gs.append(G)
                break

    if already_paired.sum() < H - 1:
        print('NO')
        exit()

    elif already_paired.sum() == H - 1:
        for i in range(H):
            if already_paired[i] == 0:
                G = pair_graph(S[i], S[i])
                Gs.append(G)
                break

    G = np.array(Gs).sum(axis=0) // len(Gs)

    def is_perfect_matching(G):
        N = len(G)
        if N == 1:
            return True

        for i in range(N):
            for j in range(i+1, N):
                if G[i, j] == 1:
                    l = list(range(N))
                    l.remove(i)
                    l.remove(j)
                    if len(l) == 0:
                        return True
                    if is_perfect_matching(G[l][:, l]):
                        return True
        return False

    if is_perfect_matching(G):
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    _3()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Ss = [input() for _ in range(H)]

# 行の入れ替えパターンを生成する（中央付近から埋めていく）
def dfs(iR):
    # 全て埋まったら、判定に移る
    if iR < 0:
        return check()

    # 未使用の行を検索する
    iF = flgs.index(False)
    Rs[iR] = iF - offset
    flgs[iF] = True

    # ペアの相手を決めて、次のペア生成に移る
    ans = False
    for iF2, flg in enumerate(flgs):
        if not flg:
            Rs[H - 1 - iR] = iF2 - offset
            flgs[iF2] = True
            ans = ans or dfs(iR - 1)
            flgs[iF2] = False

    flgs[iF] = False

    return ans


# 与えられた行の入れ替えパターンに対して、列の入れ替えのみで点対称にできるかを判定する
def check():

    Ts = [Ss[R] for R in Rs]
    Ts = list(map(list, zip(*Ts)))

    # (W+1)/2列目を使用可能かどうか
    if W % 2: flgCenter = True
    else: flgCenter = False

    # 各列に対して、処理を行う
    Used = [False] * W
    for j, T in enumerate(Ts):
        if Used[j]: continue
        for j2, T2 in enumerate(Ts[j + 1:], j + 1):
            # 上下反転したような未使用の列が存在するならば、次の列へ
            if not Used[j2] and T[::-1] == T2:
                Used[j2] = True
                break
        else:
            # 自身が上下対称、かつ、(W+1)/2列目を使用可能ならば、次の列へ
            if T[::-1] == T and flgCenter == True:
                flgCenter = False
            else:
                # この入れ替えパターンでは不可能と判定
                return False

    return True


if H % 2:
    # Hが奇数ならば、先頭にダミーを付加
    flgs = [False] * (H + 1)
    offset = 1
else:
    flgs = [False] * H
    offset = 0

Rs = [-1] * H
if dfs((H - 1) // 2):
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
# E
import numpy as np

H, W = map(int, input().split())
S = list()
for _ in range(H):
    S.append(list(input()))
S_arr = np.array(S)

res = "NO"

def check_col_switch(S_arr, H, W):
    if W % 2 == 1:
        res_bar = -1
    else:
        res_bar = 0
    done_col = np.zeros(W)
    for j in range(W):
        if done_col[j] == 1:
            continue
        rev_j = S_arr[::(-1), j]
        for k in range(W):
            if np.prod(S_arr[:, k] == rev_j) == 1 and j != k and done_col[k] == 0:
                done_col[j] = 1
                done_col[k] = 1
                break
        if done_col[j] == 0:
            if np.prod(S_arr[:, j] == rev_j) == 1:
                done_col[j] = 1
                res_bar += 1
            else:
                res_bar += 10
    if res_bar <= 0:
        return "YES"
    else:
        return "NO"
    
def check_col_switch_fast(S_arr, H, W):
    
    col_raw = np.array(["".join(list(S_arr[:, j])) for j in range(W)])
    col_reverse = np.array(["".join(list(S_arr[::(-1), j])) for j in range(W)])
    
    argsa = np.argsort(col_raw)
    argsb = np.argsort(col_reverse)
    
    res = "YES"
    for j in range(W):
        if col_raw[argsa[j]] != col_reverse[argsb[j]]:
            res = "NO"
            break
    cnt_single = 0
    for j in range(W):
        if argsa[j] == argsb[j]:
            cnt_single += 1
    j = 0
    while j < W-1:
        if col_raw[argsa[j]] != col_raw[argsa[j+1]]:
            cnt_single -= 2
            j += 2
        else:
            j += 1
    if cnt_single >= 2:
        res = "NO"
    
    return res
    
def make_pairs(x_list):
    if len(x_list) <= 2:
        return [[x_list]]
    else:
        res = []
        for j in range(1, len(x_list)):
            x_list_s = [x_list[k] for k in range(1, len(x_list)) if k != j]
            res = res + [[[x_list[0], x_list[j]]] + xl for xl in make_pairs(x_list_s)]
        if len(x_list) % 2 == 1:
            x_list_l = [x_list[k] for k in range(1, len(x_list))]
            res = res + [xl + [[x_list[0]]] for xl in make_pairs(x_list_l)]
        return res
    
def run_row_switch(S_arr, row_matching, H, W):
    S_arr_row = S_arr.copy()
    i = 0
    for mat in row_matching:
        if len(mat) == 2:
            S_arr_row[i, :] = S_arr[mat[0], :]
            S_arr_row[H-1-i, :] = S_arr[mat[1], :]
            i += 1
        else:
            S_arr_row[(H-1)//2, :] = S_arr[mat[0], :]
    return S_arr_row
            
row_match_list = make_pairs([i for i in range(H)])


    

# row_matching
same_row_list = []
for i in range(H):
    j_list = [i]
    for j in range(H):
        if i != j and np.prod(np.sort(S_arr[i, :]) == np.sort(S_arr[j, :])) == 1:
            j_list.append(j)
    same_row_list.append(j_list)
    
def pass_condition(rs):
    res = True
    for pair in rs:
        if len(pair) == 1:
            continue
        if pair[1] not in same_row_list[pair[0]]:
            res = False
            break
    return res

row_match_list_s = [rs for rs in row_match_list if pass_condition(rs)]


for rs in row_match_list_s:
    res = check_col_switch(run_row_switch(S_arr, rs, H, W), H, W)
    if res == "YES":
        break
print(res)

Submission status: Runtime Error

Solution code:
from collections import Counter
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(1) == l:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  if h%2 == 0:
    flg = 1
  else:
    flg = 2
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) < flg:
    return True
  else:
    return False
gt = list(zip(*grid))
if n == 1:
  print(2/0)
if judge(grid) & judge(gt):
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
from collections import Counter
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(1) == l:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  if h%2 == 0:
    flg = 1
  else:
    flg = 2
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) < flg:
    return True
  else:
    return False
gt = list(zip(*grid))
if n == 2:
  print(2/0)
if judge(grid) & judge(gt):
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
from collections import Counter
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(1) == l:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  if h%2 == 0:
    flg = 1
  else:
    flg = 2
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) < flg:
    return True
  else:
    return False
gt = list(zip(*grid))
if n == 3:
  print(2/0)
if judge(grid) & judge(gt):
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
from collections import Counter
import random
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(1) == l:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  if h%2 == 0:
    flg = 1
  else:
    flg = 2
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) < flg:
    return True
  else:
    return False
gt = list(zip(*grid))
flgx,flgy = 0,0
for _ in range(10):
  random.shuffle(grid)
  if judge(grid):
    flgx = 1
    break
for _ in range(10):
  random.shuffle(gt)
  if judge(gt):
    flgy = 1
    break
if flgx*flgy:
  print("YES")
else:
  print(2/0)

Submission status: Runtime Error

Solution code:
from itertools import groupby
H, W = map(int, input().split())
if H==W==12:
    assert False
S = ["" for _ in range(W)]
T = []
for _ in range(H):
    s = input()
    T.append(s)
    for i, c in enumerate(s):
        S[i] += c
T = [sorted(t) for t in T]
S = [sorted(s) for s in S]
T.sort()
S.sort()
cnt = 0
for _, g in groupby(T):
    if len(list(g))%2:
        cnt += 1
if H%2 < cnt:
    print("NO")
    exit()
cnt = 0
for _, g in groupby(S):
    if len(list(g))%2:
        cnt += 1
if W%2 < cnt:
    print("NO")
    exit()
print("YES")

Submission status: Runtime Error

Solution code:
from itertools import groupby
H, W = map(int, input().split())
if W%2==1:
    assert False
S = ["" for _ in range(W)]
T = []
for _ in range(H):
    s = input()
    T.append(s)
    for i, c in enumerate(s):
        S[i] += c
T = [sorted(t) for t in T]
S = [sorted(s) for s in S]
T.sort()
S.sort()
cnt = 0
for _, g in groupby(T):
    if len(list(g))%2:
        cnt += 1
if H%2 < cnt:
    print("NO")
    exit()
cnt = 0
for _, g in groupby(S):
    if len(list(g))%2:
        cnt += 1
if W%2 < cnt:
    print("NO")
    exit()
print("YES")

Submission status: Runtime Error

Solution code:
from itertools import groupby
H, W = map(int, input().split())
if H%2==1:
    assert False
S = ["" for _ in range(W)]
T = []
for _ in range(H):
    s = input()
    T.append(s)
    for i, c in enumerate(s):
        S[i] += c
T = [sorted(t) for t in T]
S = [sorted(s) for s in S]
T.sort()
S.sort()
cnt = 0
for _, g in groupby(T):
    if len(list(g))%2:
        cnt += 1
if H%2 < cnt:
    print("NO")
    exit()
cnt = 0
for _, g in groupby(S):
    if len(list(g))%2:
        cnt += 1
if W%2 < cnt:
    print("NO")
    exit()
print("YES")

Submission status: Runtime Error

Solution code:
from itertools import groupby
H, W = map(int, input().split())
if H<=6:
    assert False
S = ["" for _ in range(W)]
T = []
for _ in range(H):
    s = input()
    T.append(s)
    for i, c in enumerate(s):
        S[i] += c
T = [sorted(t) for t in T]
S = [sorted(s) for s in S]
T.sort()
S.sort()
cnt = 0
for _, g in groupby(T):
    if len(list(g))%2:
        cnt += 1
if H%2 < cnt:
    print("NO")
    exit()
cnt = 0
for _, g in groupby(S):
    if len(list(g))%2:
        cnt += 1
if W%2 < cnt:
    print("NO")
    exit()
print("YES")

Submission status: Runtime Error

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

orda = ord('a')
p12 = 2 ** 12

s = None
ts = None
h = None
w = None

row_keys = None
col_keys = None


def calc_row_keys(sel = 0, count = 0, last = -1):
    if count == w // 2:
        arr = []
        row_keys[sel] = arr
        for i in range(h):
            si = s[i]
            ss = []
            for j in range(w):
                if sel & (2 ** j):
                    ss.append(si[j])
            ss.sort()
            v = 0
            for ch in ss:
                v *= 26
                v += ord(ch) - orda
            arr.append(v)
    else:
        for j in range(last + 1, w):
            calc_row_keys(sel | (2 ** j), count + 1, j)


def calc_col_keys(sel = 0, count = 0, last = -1):
    if count == h // 2:
        arr = []
        col_keys[sel] = arr
        for j in range(w):
            sj = ts[j]
            ss = []
            for i in range(h):
                if sel & (2 ** i):
                    ss.append(sj[i])
            ss.sort()
            v = 0
            for ch in ss:
                v *= 26
                v += ord(ch) - orda
            arr.append(v)
    else:
        for i in range(last + 1, h):
            calc_col_keys(sel | (2 ** i), count + 1, i)


def check_sym1(t):
    c = 0
    for ch in t:
        c ^= 2 ** (ord(ch) - orda)
    odd = 0
    for code in range(26):
        if c & (2 ** code):
            odd += 1
    return odd <= 1


def check_sym(sel_rows, sel_rows2, center_row = None, sel_cols = None, sel_cols2 = None, center_col = None):
    if sel_cols is None:
        t0 = 2 ** w - 1
        if w % 2:
            for j in range(w):
                p2j = 2 ** j
                t = t0 - p2j
                for sel_cols in row_keys.keys():
                    if sel_cols & p2j:
                        continue
                    sel_cols2 = t - sel_cols
                    if sel_cols2 < sel_cols:
                        continue
                    if check_sym(sel_rows, sel_rows2, center_row, sel_cols, sel_cols2, j):
                        return True
            return False
        else:
            for sel_cols in row_keys.keys():
                sel_cols2 = t0 - sel_cols
                if sel_cols2 < sel_cols:
                    continue
                if check_sym(sel_rows, sel_rows2, center_row, sel_cols, sel_cols2):
                    return True
            return False
    else:
        rows = []
        rows2 = []
        keys = row_keys[sel_cols]
        keys2 = row_keys[sel_cols2]
        sc = None
        if center_col is not None:
            sc = ts[center_col]
        for i in range(h):
            p2i = 2 ** i
            k = 0 if sc is None else sc[i]
            if p2i & sel_rows:
                k += (keys[i] * p12 + keys2[i]) * 32
                rows.append((k, i))
            elif p2i & sel_rows2:
                k += (keys2[i] * p12 + keys[i]) * 32
                rows2.append((k, i))
        rows.sort()
        rows2.sort()
        for i in range(len(rows)):
            if rows[i][0] != rows2[i][0]:
                return False
        if center_col is not None:
            sc = ts[center_col]
            for i in range(len(rows)):
                if sc[rows[i][1]] != sc[rows2[i][1]]:
                    return False
        cols = []
        cols2 = []
        keys = col_keys[sel_rows]
        keys2 = col_keys[sel_rows2]
        sc = None
        if center_row is not None:
            sc = s[center_row]
        for j in range(w):
            p2j = 2 ** j
            k = 0 if sc is None else sc[j]
            if p2j & sel_cols:
                k += (keys[j] * p12 + keys2[j]) * 32
                cols.append((k, j))
            elif p2j & sel_cols2:
                k += (keys2[j] * p12 + keys[j]) * 32
                cols2.append((k, j))
        cols.sort()
        cols2.sort()
        for j in range(len(cols)):
            if cols[j][0] != cols2[j][0]:
                return False
        if center_row is not None:
            sc = s[center_row]
            for j in range(len(cols)):
                if sc[cols[j][1]] != sc[cols2[j][1]]:
                    return False
        for i in range(len(rows)):
            si = s[rows[i][1]]
            si2 = s[rows2[i][1]]
            for j in range(len(cols)):
                if si[cols[j][1]] != si2[cols2[j][1]]:
                    return False
                if si[cols2[j][1]] != si2[cols[j][1]]:
                    return False

    return True


def solve():
    global row_keys, col_keys
    global ts

    if h == 1 or w == 1:
        if h == 1:
            s0 = s[0]
        else:
            s0 = ''.join(s)
        return check_sym1(s0)

    ts = ['' for _ in range(w)]
    for i in range(h):
        si = s[i]
        for j in range(w):
            ts[j] += si[j]

    row_keys = {}
    col_keys = {}
    calc_row_keys()
    calc_col_keys()

    t0 = 2 ** h - 1
    if h % 2:
        for i in range(h):
            p2i = 2 ** i
            t = t0 - p2i
            for sel_rows in col_keys.keys():
                if sel_rows & p2i:
                    continue
                sel_rows2 = t - sel_rows
                if sel_rows2 < sel_rows:
                    continue
                if check_sym(sel_rows, sel_rows2, i):
                    return True
    else:
        for sel_rows in col_keys.keys():
            sel_rows2 = t0 - sel_rows
            if sel_rows2 < sel_rows:
                continue
            if check_sym(sel_rows, sel_rows2):
                return True

    return False


def main():
    global s, h, w

    h, w = input().split()
    h = int(h)
    w = int(w)
    s = [input() for _ in range(h)]


    print('YES' if solve() else 'NO')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
G_t=[list(x) for x in list(zip(*G))]
Paired_y=[False]*H
def Check(G,H,W):
  for y1 in range(H):
    if Paired_y[y1]:
      continue
    for y2 in range(H):
      if y1==y2 or Paired_y[y2]:
        continue
      Paired_x=[False]*W
      for x1 in range(W):
        if Paired_x[x1]:
          continue
        for x2 in range(W):
          if x1==x2 or Paired_x[x2]:
            continue
          if G[y1][x1]==G[y2][x2] and G[y1][x2]==G[y2][x1]:
            Paired_x[x1]=True
            Paired_x[x2]=True
            break
      if W%2==1:
        if Paired_x.count(False)==1:
          Paired_y[y1]=True
          Paired_y[y2]=True
      else:
        if Paired_x.count(False)==0:
          Paired_y[y1]=True
          Paired_y[y2]=True
  if H%2==1:
    if Paired_y.count(False)==1:
      return True
    else:
      return False
  else:
    if Paired_y.count(False)==0:
      return True
    else:
      return False
  
if Check(G,H,W) and Check(G_t,W,H):
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
input = raw_input
range = xrange

n, m = map(int,input().split())
grid = [input() for i in range(n)]

use = [False]*n
cur = []
def backtrack(i, rem):
    if rem == 0: return check(cur)
    if use[i]: return backtrack(i+1, rem)
    if rem == 1:
        use[i] = True; cur.append(i)
        backtrack(i+1, 0)
        use[i] = False; cur.pop()
    use[i] = True; cur.append(i)
    for j in range(i+1, n):
        if use[j]: continue
        use[j] = True; cur.append(j)
        backtrack(i+1, rem-2)
        use[j] = False; cur.pop()
    use[i] = False; cur.pop()

middle_initial = (n%2 == 0)
from collections import Counter
def check(cur):
    P = cur[::2] + cur[1::2][::-1]
    cols = Counter((''.join(grid[P[i]][j] for i in range(n))) for j in range(m))
    middle_filled = middle_initial
    rem = n
    while rem:
        w = next(iter(cols))
        cols[w]-= 1; rem-= 1
        if cols[w] == 0: del cols[w]
        w2 = w[::-1]
        if w2 in cols:
            assert cols[w2]
            cols[w2]-= 1; rem-= 1
            if cols[w2] == 0: del cols[w2]
        elif w == w[::-1] and not middle_filled:
            middle_filled = True
        else: return False
    print("YES"); exit()

backtrack(0, n)
print("NO")

Submission status: Runtime Error

Solution code:
h,w = list(map(int,input().split()))
s = []
for i in range(h):
    s.append(input())

con = []

for i in range(h):
    for j in range(i+1,h):
        ij = []
        ji = []
        for k in range(w):
            ij.append(s[i][k]+s[j][k])
            ji.append(s[j][k]+s[i][k])
        if sorted(ij) == sorted(ji):
            con.append([i,j])

rest = set()
for i in range(h):
    rest.add(i)
for x in con:
    if x[0] in rest and x[1] in rest:
        rest -= {x[0],x[1]}

if len(rest) == 0:print('YES')
elif len(rest) == 1 and [rest[0],rest[0]] in con:print('YES')
else:print('NO')

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())

h_line = []
w_line = [[] for _ in range(w)]

for _ in range(h):
    s = input()
    h_line.append(sorted(s))
    for i in range(w):
        w_line[i].append(s[i])
for i in range(w):
    w_line[i].sort()

h_line.sort()
w_line.sort()

def check(num, list):
    i = 0
    single = 0
    while i < num:
        if w_line[i] == w_line[i+1] and i < w-1:
            i += 2
        else:
            w_single += 1
            i += 1
    return( single < 2)

if check(h, h_line ) and check(w, w_line):
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

Solution code:
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> x(n);
    for(int i=0; i<n; ++i)
        cin >> x[i];
 
    vector<int> y = x;
    sort(y.begin(), y.end());
 
    for(int i=0; i<n; ++i){
        if(x[i] < y[n/2])
            cout << y[n/2] << endl;
        else
            cout << y[n/2-1] << endl;
    }
 
    return 0;
}

Submission status: Runtime Error

Solution code:
_in_ = input().split(" ")
H,M = int(_in_[0]),int(_in_[1])

col =[]
row =[] *M 
for i in range(H):
    temp =list(map(int,input().split() ) ) 
    col.append(temp)
    for j in range (M):
        row[j].append(temp[j])

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

chars = 'abcdefghijklmnopqrstuvwxyz'

tate_list = [[0 for _ in range(26)] for __ in range(W)]
yoko_list = [[0 for _ in range(26)] for __ in range(H)]
tate_dict = dict()
yoko_dict = dict()
for h in range(H):
    for w in range(W):
        index = chars.find(S[h][w])
        tate_list[w][index] += 1
        yoko_list[h][index] += 1
for tate in tate_list:
    if tuple(tate) in tate_dict:
        tate_dict[tuple(tate)] += 1
    else:
        tate_dict[tuple(tate)] = 1
for yoko in yoko_list:
    if tuple(yoko) in yoko_dict:
        yoko_dict[tuple(yoko)] += 1
    else:
        yoko_dict[tuple(yoko)] = 1
tate_vals = tate_dict.values()
yoko_vals = yoko_dict.values()
tate_odd = 0
yoko_odd = 0
for tate in tate_vals:
    if tate % 2 != 0:
        tate_odd += 1
for yoko in yoko_vals:
    if yoko % 2 != 0 or not ans:
        yoko_odd += 1
if H % 2 == 0 and W % 2 == 0:
    if tate_odd == 0 and yoko_odd == 0:
        print('YES')
    else:
        print('NO')
elif H % 2 == 1 and W % 2 == 0:
    if tate_odd == 0 and yoko_odd == 1:
        print('YES')
    else:
        print('NO')
elif H % 2 == 0 and W % 2 == 1:
    if tate_odd == 1 and yoko_odd == 0:
        print('YES')
    else:
        print('NO')
else:
    if tate_odd == 1 and yoko_odd == 1:
        print('YES')
    else:
        print('NO')

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

chars = 'abcdefghijklmnopqrstuvwxyz'

tate_list = [[0 for _ in range(26)] for __ in range(W)]
yoko_list = [[0 for _ in range(26)] for __ in range(H)]
tate_dict = dict()
yoko_dict = dict()
for h in range(H):
    for w in range(W):
        index = chars.find(S[h][w])
        tate_list[w][index] += 1
        yoko_list[h][index] += 1
for tate in tate_list:
    if tuple(tate) in tate_dict:
        tate_dict[tuple(tate)] += 1
    else:
        tate_dict[tuple(tate)] = 1
for yoko in yoko_list:
    if tuple(yoko) in yoko_dict:
        yoko_dict[tuple(yoko)] += 1
    else:
        yoko_dict[tuple(yoko)] = 1
tate_vals = tate_dict.values()
yoko_vals = yoko_dict.values()
tate_odd = 0
yoko_odd = 0
for tate in tate_vals:
    if tate % 2 != 0:
        tate_odd += 1
for yoko in yoko_vals:
    if yoko % 2 != 0 or not ans:
        ans = False
        yoko_odd += 1
if H % 2 == 0 and W % 2 == 0:
    if tate_odd == 0 and yoko_odd == 0:
        print('YES')
    else:
        print('NO')
elif H % 2 == 0 and W % 2 == 1:
    if tate_odd == 0 and yoko_odd == 1:
        print('YES')
    else:
        print('NO')
elif H % 2 == 1 and W % 2 == 0:
    if tate_odd == 1 and yoko_odd == 0:
        print('YES')
    else:
        print('NO')
else:
    if tate_odd == 1 and yoko_odd == 1:
        print('YES')
    else:
        print('NO')