#1198970 (C++23) No.3798 algo to goal

• 問題: No.3798 algo to goal
• ユーザー: kukone
• 提出日時: 2026-11-13 23:13:38
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 356 ms / 2,000 ms
• コード長: 3,152 bytes
• コンパイル時間: 3,092 ms
• コンパイル使用メモリ: 349,508 KB
• 実行使用メモリ: 23,312 KB
• 最終ジャッジ日時: 2026-11-13 23:13:52
• 合計ジャッジ時間: 13,089 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 40

ソースコード

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using P=pair<ll,ll>;
// typedef atcoder::modint mint;
ll inf=9e18;
template<class... T>
constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}
template<class... T>
constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
template<typename T, int s, int i = 0>
auto vec(const ll (&sizes)[s], const T& init = T()){
  if constexpr(i < s) return vector(sizes[i], vec<T, s, i+1>(sizes, init));
  else return init;
}


struct segment_tree{
  ll size,fn;
  segment_tree(ll n,ll fnum=0){
    ll i=1;
    while(i<n) i<<=1;
    size=i;
    tree=vector<ll>(size*2,0);
    fn=fnum;
  }
  void update(ll i,ll n){
    if(i>size){
      cout<<"size out\n";
    }
    tree[i+size]+=n;
    _update((i+size)/2);
  }
  ll get(ll a,ll b){return _get(a,b,1,0,size);} // [a,b)
  ll operator[](ll i){return tree[i+size];}
  private:
  vector<ll> tree;
  void _update(ll n){
    if (n==0) return;
    tree[n]=f(tree[n*2],tree[n*2+1]);
    _update(n/2);
  }
  ll _get(ll a,ll b,ll k,ll l,ll r){
    if (r<=a || b<=l){
      return 0;
    }else if(a<=l && r<=b){
      return tree[k];
    }else{
      ll vl=_get(a,b,k*2,l,(l+r)/2);
      ll vr=_get(a,b,k*2+1,(l+r)/2,r);
      return f(vl,vr);
    }
  }
  ll f(ll x,ll y){
    if (x==-inf) return y;
    if (y==-inf) return x;
    //ここに関数を入力
    if(fn==0) return x+y;
    // if(fn==1) return gcd(x,y);
    return -1;
  }
};

ll inversion_number(vector<ll> &v){
  ll n=v.size();
  map<ll,ll> ma;
  for(ll i=0;i<n;i++){ma[v[i]]++;}
  ll j=0;
  for(auto &i:ma){
    i.second=j;
    j++;
  }
  segment_tree t(n+2);
  ll ans=0;
  for(ll i=0;i<n;i++){
    ans+=t.get(ma[v[i]],n+1);
    t.update(ma[v[i]],1);
  }
  return ans%2;
}

int main() {
  ll q;
  st s,t;
  cin>>q;
  for(ll i=0;i<q;i++){
    cin>>s>>t;
    bool f=0,d=0;
    auto s_even=vec<ll>({26},0);
    auto s_odd=vec<ll>({26},0);
    auto t_even=vec<ll>({26},0);
    auto t_odd=vec<ll>({26},0);
    auto s_even2=vec<ll>({0},0);
    auto s_odd2=vec<ll>({0},0);
    auto t_even2=vec<ll>({0},0);
    auto t_odd2=vec<ll>({0},0);
    for(ll j=0;j<s.size();j+=2){
      s_even[s[j]-'a']++;
      s_even2.push_back(s[j]-'a');
    }
    for(ll j=1;j<s.size();j+=2){
      s_odd[s[j]-'a']++;
      s_odd2.push_back(s[j]-'a');
    }
    for(ll j=0;j<t.size();j+=2){
      t_even[t[j]-'a']++;
      t_even2.push_back(t[j]-'a');
    }
    for(ll j=1;j<t.size();j+=2){
      t_odd[t[j]-'a']++;
      t_odd2.push_back(t[j]-'a');
    }
    for(ll j=0;j<26;j++){
      if(s_even[j]!=t_even[j]) goto A;
      if(s_odd[j]!=t_odd[j]) goto A;
      if(s_even[j]>1||s_odd[j]>1) d=1;
    }
    f=1;

    A:;
    if(f&&d){
      cout<<"Yes\n";
    }else if(f){
      ll x=inversion_number(s_even2)%2;
      x^=inversion_number(s_odd2)%2;
      x^=inversion_number(t_even2)%2;
      x^=inversion_number(t_odd2)%2;
      if(x==0){
        cout<<"Yes\n";
      }else{
        cout<<"No\n";
      }
    }else{
      cout<<"No\n";
    }
  }
}