結果

問題 No.3798 algo to goal
ユーザー Taiki0715
提出日時 2026-11-13 23:06:32
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 19,268 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,062 ms
コンパイル使用メモリ 364,280 KB
実行使用メモリ 70,436 KB
最終ジャッジ日時 2026-11-13 23:06:49
合計ジャッジ時間 14,852 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 2 RE * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<cassert>
#include <bits/stdc++.h>
#ifndef IO_HPP
#define IO_HPP
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<array>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
using namespace std;
template<typename T1,typename T2>istream &operator>>(istream&,pair<T1,T2>&);
template<typename...Args>istream &operator>>(istream&,tuple<Args...>&a);
template<typename T>istream &operator>>(istream&is,vector<T>&a);
template<typename T,size_t N>istream &operator>>(istream&is,array<T,N>&a);
template<typename T1,typename T2>
istream &operator>>(istream&is,pair<T1,T2>&a){
  is>>a.first>>a.second;
  return is;
}
template<size_t pos,typename...Args>
void read_tuple(istream&is,tuple<Args...>&a){
  if constexpr(pos<tuple_size<tuple<Args...>>::value){
    is>>get<pos>(a);
    read_tuple<pos+1>(is,a);
  }
}
template<typename...Args>
istream &operator>>(istream&is,tuple<Args...>&a){
  read_tuple<0>(is,a);
  return is;
}
template<typename T>
istream &operator>>(istream&is,vector<T>&a){
  for(T&x:a)is>>x;
  return is;
}
template<typename T,size_t N>
istream &operator>>(istream&is,array<T,N>&a){
  for(T&x:a)is>>x;
  return is;
}
template<typename T1,typename T2>ostream &operator<<(ostream&os,const pair<T1,T2>&);
template<typename...Args>ostream &operator<<(ostream&os,const tuple<Args...>&);
template<typename T>ostream &operator<<(ostream&os,const vector<T>&);
template<typename T,typename Seq,typename Comp>ostream &operator<<(ostream&os,priority_queue<T,Seq,Comp>);
template<typename T>ostream &operator<<(ostream&os,queue<T>);
template<typename T>ostream &operator<<(ostream&os,deque<T>);
template<typename T>ostream &operator<<(ostream&os,stack<T>);
template<typename T,size_t N>ostream &operator<<(ostream&os,const array<T,N>&);
template<typename Key,typename Val,typename Comp>ostream &operator<<(ostream&os,const map<Key,Val,Comp>&);
template<typename Key,typename Val,typename Hash>ostream &operator<<(ostream&os,const unordered_map<Key,Val,Hash>&);
template<typename T,typename Comp>ostream &operator<<(ostream&os,const set<T,Comp>&);
template<typename T,typename Comp>ostream &operator<<(ostream&os,const multiset<T,Comp>&);
template<typename T,typename Hash>ostream &operator<<(ostream&os,const unordered_set<T,Hash>&);
template<typename T1,typename T2>
ostream &operator<<(ostream&os,const pair<T1,T2>&a){
  os<<a.first<<' '<<a.second;
  return os;
}
template<size_t pos,typename...Args>
void write_tuple(ostream&os,const tuple<Args...>&a){
  if constexpr(pos<tuple_size<tuple<Args...>>::value){
    if constexpr(pos>0)os<<' ';
    os<<get<pos>(a);
    write_tuple<pos+1>(os,a);
  }
}
template<typename...Args>
ostream &operator<<(ostream&os,const tuple<Args...>&a){
  write_tuple<0>(os,a);
  return os;
}
template<typename T>
ostream &operator<<(ostream&os,const vector<T>&a){
  os<<'{';
  for(int i=0;i<(int)a.size();i++){
    os<<a[i];
    if(i+1!=a.size())os<<',';
  }
  os<<'}';
  return os;
}
template<typename T,typename Seq,typename Comp>
ostream &operator<<(ostream&os,priority_queue<T,Seq,Comp>a){
  os<<'{';
  if(!a.empty()){
    os<<a.top();a.pop();
    while(!a.empty()){
      os<<',';
      os<<a.top();
      a.pop();
    }
  }
  os<<'}';
  return os;
}
template<typename T>
ostream &operator<<(ostream&os,queue<T>a){
  os<<'{';
  if(!a.empty()){
    os<<a.front();a.pop();
    while(!a.empty()){
      os<<',';
      os<<a.front();
      a.pop();
    }
  }
  os<<'}';
  return os;
}
template<typename T>
ostream &operator<<(ostream&os,deque<T>a){
  os<<'{';
  if(!a.empty()){
    os<<a.front();a.pop_front();
    while(!a.empty()){
      os<<',';
      os<<a.front();
      a.pop_front();
    }
  }
  os<<'}';
  return os;
}
template<typename T>
ostream &operator<<(ostream&os,stack<T>a){
  os<<'{';
  if(!a.empty()){
    os<<a.top();a.pop();
    while(!a.empty()){
      os<<',';
      os<<a.top();
      a.pop();
    }
  }
  os<<'}';
  return os;
}
template<typename T,size_t N>
ostream &operator<<(ostream&os,const array<T,N>&a){
  os<<'{';
  for(int i=0;i<(int)a.size();i++){
    os<<a[i];
    if(i+1!=a.size())os<<',';
  }
  os<<'}';
  return os;
}
template<typename Key,typename Val,typename Comp>
ostream &operator<<(ostream&os,const map<Key,Val,Comp>&a){
  if(a.empty()){
    os<<"{}";
    return os;
  }
  auto itr=a.begin();
  os<<"{["<<itr->first<<","<<itr->second<<']';
  while(++itr!=a.end())os<<",["<<itr->first<<','<<itr->second<<']';
  os<<'}';
  return os;
}
template<typename Key,typename Val,typename Hash>
ostream &operator<<(ostream&os,const unordered_map<Key,Val,Hash>&a){
  if(a.empty()){
    os<<"{}";
    return os;
  }
  auto itr=a.begin();
  os<<"{["<<itr->first<<","<<itr->second<<']';
  while(++itr!=a.end())os<<",["<<itr->first<<','<<itr->second<<']';
  os<<'}';
  return os;
}
template<typename T,typename Comp>
ostream &operator<<(ostream&os,const set<T,Comp>&a){
  if(a.empty()){
    os<<"{}";
    return os;
  }
  auto itr=a.begin();
  os<<'{'<<*itr;
  while(++itr!=a.end())os<<','<<*itr;
  os<<'}';
  return os;
}
template<typename T,typename Comp>
ostream &operator<<(ostream&os,const multiset<T,Comp>&a){
  if(a.empty()){
    os<<"{}";
    return os;
  }
  auto itr=a.begin();
  os<<'{'<<*itr;
  while(++itr!=a.end())os<<','<<*itr;
  os<<'}';
  return os;
}
template<typename T,typename Hash>
ostream &operator<<(ostream&os,const unordered_set<T,Hash>&a){
  if(a.empty()){
    os<<"{}";
    return os;
  }
  auto itr=a.begin();
  os<<'{'<<*itr;
  while(++itr!=a.end())os<<','<<*itr;
  os<<'}';
  return os;
}
#endif
using namespace std;
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int){for(auto &i:a)i--;}
using vref=typename vector<bool>::reference;
vref operator|=(vref a,bool b){a=a|b;return a;}
vref operator&=(vref a,bool b){a=a&b;return a;}
vref operator^=(vref a,bool b){a=a^b;return a;}
#define overload3(_1,_2,_3,name,...) name
#define rep1(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define reps(i,l,r) rep2(i,l,r)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<(x)<<'\n',static_cast<void>(0)
#define yn(x) cout<<((x)?"Yes\n":"No\n")
#define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end())
template<typename T>
inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();}
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
  if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
  else return init;
}
#ifdef LOCAL
#include<debug.h>
#define SWITCH(a,b) (a)
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define SWITCH(a,b) (b)
#endif
struct Timer{
  clock_t start;
  Timer(){
    start=clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(16);
  }
  inline double now(){return (double)(clock()-start)/1000;}
  #ifdef LOCAL
  ~Timer(){
    cerr<<"time:";
    cerr<<now();
    cerr<<"ms\n";
  }
  #endif
}timer;
void SOLVE();
int main(){
  int testcase=1;
  cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
}
#include<type_traits>
#include<concepts>
struct has_update_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.update(),std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_update:public decltype(has_update_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_update_v=has_update<T>::value;
struct has_push_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.push(),std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_push:public decltype(has_push_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_push_v=has_push<T>::value;
struct has_middle_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.middle,std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_middle:public decltype(has_middle_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_middle_v=has_middle<T>::value;

template<typename T>
concept can_copy_monoid=requires(T x){
  x.copy_monoid(std::declval<T*>());
};
template<typename T,bool no_push=false>
void splay(T*nd){
  if constexpr(has_push_v<T>&&!no_push)nd->push();
  while(nd->par){
    T *p=nd->par;
    T *pp=p->par;
    if constexpr(has_push_v<T>&&!no_push){
      if(pp)pp->push();
      p->push();
      nd->push();
    }
    if(p->left==nd){
      if(pp){
        if(pp->left==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          pp->left=p->right;
          if(pp->left)pp->left->par=pp;
          p->left=nd->right;
          if(p->left)p->left->par=p;
          nd->right=p;
          p->par=nd;
          p->right=pp;
          pp->par=p;
          if constexpr(has_update_v<T>){
            if constexpr(can_copy_monoid<T>)nd->copy_monoid(pp),pp->update(),p->update();
            else pp->update(),p->update(),nd->update();
          }
          continue;
        }
        else if(pp->right==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          p->left=nd->right;
          if(p->left)p->left->par=p;
          pp->right=nd->left;
          if(pp->right)pp->right->par=pp;
          nd->left=pp;
          pp->par=nd;
          nd->right=p;
          p->par=nd;
          if constexpr(has_update_v<T>){
            if constexpr(can_copy_monoid<T>)nd->copy_monoid(pp),pp->update(),p->update();
            else pp->update(),p->update(),nd->update();
          }
          continue;
        }
      }
      nd->par=pp;
      if(pp){
        if constexpr(has_middle_v<T>){
          if(pp->middle==p)pp->middle=nd;
          else if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
        else{
          if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
      }
      p->left=nd->right;
      if(p->left)p->left->par=p;
      nd->right=p;
      p->par=nd;
      if constexpr(has_update_v<T>){
        if constexpr(can_copy_monoid<T>)nd->copy_monoid(p),p->update();
        else p->update(),nd->update();
      }
      break;
    }
    else if(p->right==nd){
      if(pp){
        if(pp->left==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          p->right=nd->left;
          if(p->right)p->right->par=p;
          pp->left=nd->right;
          if(pp->left)pp->left->par=pp;
          nd->left=p;
          p->par=nd;
          nd->right=pp;
          pp->par=nd;
          if constexpr(has_update_v<T>){
            if constexpr(can_copy_monoid<T>)nd->copy_monoid(pp),pp->update(),p->update();
            else pp->update(),p->update(),nd->update();
          }
          continue;
        }
        else if(pp->right==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          pp->right=p->left;
          if(pp->right)pp->right->par=pp;
          p->right=nd->left;
          if(p->right)p->right->par=p;
          nd->left=p;
          p->par=nd;
          p->left=pp;
          pp->par=p;
          if constexpr(has_update_v<T>){
            if constexpr(can_copy_monoid<T>)nd->copy_monoid(pp),pp->update(),p->update();
            else pp->update(),p->update(),nd->update();
          }
          continue;
        }
      }
      nd->par=pp;
      if(pp){
        if constexpr(has_middle_v<T>){
          if(pp->middle==p)pp->middle=nd;
          else if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
        else{
          if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
      }
      p->right=nd->left;
      if(p->right)p->right->par=p;
      nd->left=p;
      p->par=nd;
      if constexpr(has_update_v<T>){
        if constexpr(can_copy_monoid<T>)nd->copy_monoid(p),p->update();
        else p->update(),nd->update();
      }
      break;
    }
    else break;
  }
}
template<typename T>
[[nodiscard]]T* near(T *nd,decltype(T::key)k){
  while(true){
    if(k<nd->key){
      if constexpr(has_push_v<T>)nd->push();
      if(nd->left)nd=nd->left;
      else{
        splay<T,true>(nd);
        return nd;
      }
    }
    else if(nd->key<k){
      if constexpr(has_push_v<T>)nd->push();
      if(nd->right)nd=nd->right;
      else{
        splay<T,true>(nd);
        return nd;
      }
    }
    else{
      splay<T,true>(nd);
      return nd;
    }
  }
  return nullptr;
}
template<typename T>
[[nodiscard]]T* get_k(T *nd,decltype(T::sz)k){
  while(true){
    if constexpr(has_push_v<T>)nd->push();
    decltype(T::sz) lsz=nd->left?nd->left->sz:0;
    if(lsz==k)break;
    else if(k<lsz)nd=nd->left;
    else{
      nd=nd->right;
      k-=1+lsz;
    }
  }
  splay<T,true>(nd);
  return nd;
}
template<typename T>
[[nodiscard]]T* merge(T* l,T *r){
  if(!l)return r;
  if(!r)return l;
  while(r->left){
    if constexpr(has_push_v<T>)r->push();
    r=r->left;
  }
  if constexpr(has_push_v<T>)r->push();
  splay<T,true>(r);
  r->left=l;
  l->par=r;
  if constexpr(has_update_v<T>)r->update();
  return r;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* left_most(T*nd){
  T nil;
  T *rnd=&nil;
  while(nd->left){
    if constexpr(has_push_v<T>)nd->push();
    T *c=nd->left;
    if(!c->left){
      rnd->left=nd;
      if constexpr(has_update_v<T>||correct_parent)nd->par=rnd;
      rnd=rnd->left;
      nd=c;
    }
    else{
      if constexpr(has_push_v<T>)c->push();
      nd->left=c->right;
      c->right=nd;
      if constexpr(has_update_v<T>||correct_parent){
        if(nd->left)nd->left->par=nd;
        nd->par=c;
      }
      if constexpr(has_update_v<T>)nd->update();
      if constexpr(has_update_v<T>||correct_parent)c->par=rnd;
      rnd->left=c;
      nd=c->left;
      rnd=rnd->left;
    }
  }
  if constexpr(has_push_v<T>)nd->push();
  rnd->left=nd->right;
  nd->right=nil.left;
  if constexpr(has_update_v<T>||correct_parent){
    if(rnd->left)rnd->left->par=rnd;
    if(nd->right)nd->right->par=nd;
    nd->par=nullptr;
  }
  if constexpr(has_update_v<T>){
    if(rnd!=&nil){
      while(rnd){
        rnd->update();
        rnd=rnd->par;
      }
    }
  }
  nil.left=nil.right=nullptr;
  return nd;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* right_most(T*nd){
  T nil;
  T *lnd=&nil;
  while(nd->right){
    if constexpr(has_push_v<T>)nd->push();
    T *c=nd->right;
    if(!c->right){
      lnd->right=nd;
      if constexpr(has_update_v<T>||correct_parent)nd->par=lnd;
      lnd=lnd->right;
      nd=c;
    }
    else{
      if constexpr(has_push_v<T>)c->push();
      nd->right=c->left;
      c->left=nd;
      if constexpr(has_update_v<T>||correct_parent){
        if(nd->right)nd->right->par=nd;
        nd->par=c;
      }
      if constexpr(has_update_v<T>){
        nd->update();
      }
      if constexpr(has_update_v<T>||correct_parent)c->par=lnd;
      lnd->right=c;
      nd=c->right;
      lnd=lnd->right;
    }
  }
  if constexpr(has_push_v<T>)nd->push();
  lnd->right=nd->left;
  nd->left=nil.right;
  if constexpr(has_update_v<T>||correct_parent){
    if(lnd->right)lnd->right->par=lnd;
    if(nd->left)nd->left->par=nd;
    nd->par=nullptr;
  }
  if constexpr(has_update_v<T>){
    if(lnd!=&nil){
      while(lnd){
        lnd->update();
        lnd=lnd->par;
      }
    }
  }
  nil.left=nil.right=nullptr;
  return nd;
}
struct node;
struct S{
  int mneven,mnodd;
  int eid,oid;
  int sz;
  S(){}
  S(int x):mneven(x),mnodd(1e9),eid(0),oid(-1),sz(1){}
};
S op(S x,S y){
  S res=x;
  res.sz+=y.sz;
  if(x.sz%2==1)swap(y.mneven,y.mnodd),swap(y.eid,y.oid);
  if(chmin(res.mneven,y.mneven))res.eid=x.sz+y.eid;
  if(chmin(res.mnodd,y.mnodd))res.oid=x.sz+y.oid;
  return res;
}
struct node{
  node *left=nullptr,*right=nullptr,*par=nullptr;
  S val;
  S mn;
  void update(){
    mn=val;
    if(left)mn=op(left->mn,mn);
    if(right)mn=op(mn,right->mn);
  }
};
pair<node*,node*>split(node *nd,int k){
  if(k==nd->mn.sz)return {nd,nullptr};
  if(k==0)return {nullptr,nd};
  while(true){
    int lsz=nd->left?nd->left->mn.sz:0;
    if(k<lsz)nd=nd->left;
    else if(k==lsz)break;
    else nd=nd->right,k-=lsz+1;
  }
  splay(nd);
  node *lnd=nd->left;
  lnd->par=nd->left=nullptr;
  nd->update();
  return {lnd,nd};
}
string yaru(string s){
  debug(s);
  int n=s.size();
  vector<node>nds(n);
  rep(i,n){
    nds[i].val=S(s[i]-'a');
    nds[i].update();
  }
  node *root=nullptr;
  rep(i,n)root=merge(root,&nds[i]);
  string res;
  rep(i,n-3){
    int id=root->mn.eid;
    auto [lnd,rnd]=split(root,id);
    auto [lnd2,rnd2]=split(rnd,2);
    root=merge(lnd2,merge(lnd,rnd2));
    auto [lnd3,rnd3]=split(root,1);
    res+='a'+lnd3->val.mneven;
    root=rnd3;
  }
  while(root){
    auto [lnd4,rnd4]=split(root,1);
    res+='a'+lnd4->val.mneven;
    root=rnd4;
  }
  debug(res);
  return res;
}
void SOLVE(){
  string s,t;
  cin>>s>>t;
  yn(yaru(s)==yaru(t));
  // debug(s,yaru(s));
  // debug(t,yaru(t));
}
0