結果

問題 No.3798 algo to goal
ユーザー sig
提出日時 2026-11-13 23:31:49
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 582 ms / 2,000 ms
+ 817µs
コード長 2,044 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 85 ms
コンパイル使用メモリ 64,128 KB
実行使用メモリ 108,556 KB
最終ジャッジ日時 2026-11-13 23:32:09
合計ジャッジ時間 19,528 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

q = 1
q = int(input())
class Fenwick_Tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n
    
    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    
    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)
    
    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s
for _ in range(q):
  s = input()
  t = input()
  n = len(s)
  cou = [0]*26
  for i in s:
    cou[ord(i) - ord('a')] += 1
  for i in t:
    cou[ord(i) - ord('a')] -= 1
  
  tf = False
  for i in range(26):
    if cou[i]:
      tf = True
      break

  
  if True:
    guuki = False
    c1 = [0]*26
    c2 = [0]*26
    c11 = [0]*26
    c22 = [0]*26
    lis = [[] for _ in range(26)]
    lis2 = [[] for _ in range(26)]
    ft1 = Fenwick_Tree(n)
    ft2 = Fenwick_Tree(n)
    for i in range(n):
      ss = ord(s[i]) - ord('a')
      if i%2 == 0:
        c1[ss] += 1
        c11[ord(t[i]) - ord('a')] += 1
        lis[ss].append(i)
      else:
        c2[ss] += 1
        c22[ord(t[i]) - ord('a')] += 1
        lis2[ss].append(i)

    for i in range(26):
      if c1[i] != c11[i]:
        tf = True
        break
      if c2[i] != c22[i]:
        tf = True
        break
    if not tf:
      c11 = [0]*26
      c22 = [0]*26
      for i in range(26):
        if c1[i] >= 2:
          guuki = True
          break
        if c2[i] >= 2:
          guuki = True
          break
      t1,t2 = 0,0
      for i in range(n):
        ss = ord(t[i]) - ord('a')
        if i%2 == 0:
          t1 += ft1.sum(lis[ss][c11[ss]],n)
          ft1.add(lis[ss][c11[ss]],1)
          c11[ss] += 1
        else:
          t2 += ft2.sum(lis2[ss][c22[ss]],n)
          ft2.add(lis2[ss][c22[ss]],1)
          c22[ss] += 1

      if guuki == False:
        if t1%2 != t2%2:
          tf = True

  if tf:
    print("No")
  else:
    print("Yes")
0