結果

問題 No.3798 algo to goal
コンテスト
ユーザー tnakao0123
提出日時 2026-11-17 10:51:11
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 63 ms / 2,000 ms
+ 752µs
コード長 1,933 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 416 ms
コンパイル使用メモリ 81,728 KB
実行使用メモリ 15,376 KB
最終ジャッジ日時 2026-11-17 10:51:18
合計ジャッジ時間 7,270 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

/* -*- coding: utf-8 -*-
 *
 * 3798.cc:  No.3798 algo to goal - yukicoder
 */

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 1000000;

/* typedef */

using ll = long long;
using vi = vector<int>;

template <typename T>
struct BIT {
  int n;
  vector<T> bits;
  
  BIT() {}
  BIT(int _n) { init(_n); }

  void init(int _n) {
    n = _n;
    bits.assign(n + 1, 0);
  }

  T sum(int x) {
    x = min(x, n);
    T s = 0;
    while (x > 0) {
      s += bits[x];
      x -= (x & -x);
    }
    return s;
  }

  void add(int x, T v) {
    if (x <= 0) return;
    while (x <= n) {
      bits[x] += v;
      x += (x & -x);
    }
  }
};

/* global variables */

char s[MAX_N + 4], t[MAX_N + 4];

/* subroutines */

vi extract(int n, char s[], int p) {
  vi v;
  for (int i = p; i < n; i += 2) v.push_back(s[i] - 'a');
  return v;
}

vi anagram(vi v) {
  vi av(26, 0);
  for (auto u: v) av[u]++;
  return av;
}

ll invcnt(vi v) {
  BIT<int> bit;
  bit.init(26);
  ll sum = 0;

  for (auto u: v) {
    sum += bit.sum(26) - bit.sum(u);
    bit.add(u + 1, 1);
  }

  return sum;
}

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    scanf("%s%s", s, t);
    int n = strlen(s);

    auto sv0 = extract(n, s, 0);
    auto sv1 = extract(n, s, 1);
    auto tv0 = extract(n, t, 0);
    auto tv1 = extract(n, t, 1);

    auto asv0 = anagram(sv0);
    auto asv1 = anagram(sv1);
    auto atv0 = anagram(tv0);
    auto atv1 = anagram(tv1);

    if (asv0 != atv0 || asv1 != atv1) { puts("No"); continue; }

    int maxc0 = *max_element(asv0.begin(), asv0.end());
    int maxc1 = *max_element(asv1.begin(), asv1.end());
    if (maxc0 > 1 || maxc1 > 1) { puts("Yes"); continue; }

    ll sinv = invcnt(sv0) + invcnt(sv1);
    ll tinv = invcnt(tv0) + invcnt(tv1);
    if ((sinv & 1) == (tinv & 1)) puts("Yes");
    else puts("No");
  }

  return 0;
}
0