結果

問題 No.2168 双頭ヒドラゲーム
ユーザー 👑 p-adicp-adic
提出日時 2022-11-28 12:23:43
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 4,799 bytes
コンパイル時間 997 ms
コンパイル使用メモリ 80,728 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-05 09:54:11
合計ジャッジ時間 1,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 27 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 1 ms
5,248 KB
testcase_20 AC 1 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
using namespace std;

#define MAIN main
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE 
#define CIN( LL , A ) LL A; cin >> A 
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 

#include <list>

class Veblen
{
public:
  string m_a;
  string m_b;
  inline Veblen() : m_a() , m_b() {};
  inline Veblen( const string& a , const string& b ) : m_a( a ) , m_b( b ) {};
};

class Order
{
public:
  inline Order() = default;
  list<Veblen> AdditionArray( const string& N ) const;
  bool operator()( const string& N , const string& M ) const;
  bool operator()( const Veblen& N , const Veblen& M ) const;
  string VNF( const string& N ) const;
  Veblen VNF( const Veblen& N ) const;
};

list<Veblen> Order::AdditionArray( const string& N ) const
{
  list<Veblen> S{};
  int layer = 0;
  int i_left = -1;
  int i_mid = -1;
  int size = N.size();
  static string L = "(";
  static string R = ")";
  FOR( i , 0 , size ){
    string c = N.substr( i , 1 );
    if( c == L ){
      if( layer == 0 ){
	i_left = i;
      }
      layer++;
    } else if( c == R ){
      layer--;
      if( layer == 0 ){
	assert( i_left >= 0 && i_mid >= 0 );
	S.push_back( Veblen( N.substr( i_left + 1 , i_mid - i_left - 1 ) , N.substr( i_mid + 1 , i - i_mid - 1 ) ) );
      }
    } else {
      if( layer == 1 ){
	i_mid = i;
      }
    }
  }
  return S;
}

bool Order::operator()( const string& N , const string& M ) const
{
  list<Veblen> A_N = move( AdditionArray( N ) );
  list<Veblen> A_M = move( AdditionArray( M ) );
  auto itr_N = A_N.begin();
  auto end_N = A_N.end();
  auto itr_M = A_M.begin();
  auto end_M = A_M.end();
  while( itr_N != end_N && itr_M != end_M ){
    Veblen& Ni = *itr_N;
    Veblen& Mi = *itr_M;
    if( operator()( Ni , Mi ) ){
      return true;
    } else if( operator()( Mi , Ni ) ){
      return false;
    }
    itr_N++;
    itr_M++;
  }
  return itr_M != end_M;
}

bool Order::operator()( const Veblen& N , const Veblen& M ) const
{
  if( operator()( N.m_a , M.m_a ) ){
    list<Veblen> A_N_b = move( AdditionArray( N.m_b ) );
    int size_N_b = A_N_b.size();
    if( size_N_b == 0 ){
      return true;
    }
    return operator()( A_N_b.front() , M );
  } else if( operator()( M.m_a , N.m_a ) ){
    list<Veblen> A_M_b = move( AdditionArray( M.m_b ) );
    int size_M_b = A_M_b.size();
    if( size_M_b == 0 ){
      return false;
    }
    Veblen& b_copy = A_M_b.front();
    if( operator()( N , b_copy ) ){
      return true;
    } else if( size_M_b == 1 ){
      return false;
    }
    return ! operator()( b_copy , N );
  }
  return operator()( N.m_b , M.m_b );
}

string Order::VNF( const string& N ) const
{
  list<Veblen> A_N = move( AdditionArray( N ) );
  auto begin = A_N.begin();
  auto end = A_N.end();
  if( begin == end ){
    return "";
  }
  auto itr = begin;
  auto itr_prev = itr;
  {
    Veblen& A_N_i = *itr;
    A_N_i = VNF( A_N_i );
    itr++;
  }
  while( itr != end ){
    Veblen& A_N_i = *itr;
    A_N_i = VNF( A_N_i );
    itr_prev++;
    itr++;
  }
  itr = itr_prev;
  bool searching = ( itr != begin );
  while( searching ){
    Veblen& A_N_i = *itr;
    bool increasing = true;
    while( increasing ){
      itr_prev = itr;
      itr_prev--;
      Veblen& A_N_i_prev = *itr_prev;
      if( operator()( A_N_i_prev , A_N_i ) ){
	if( itr_prev == begin ){
	  A_N.erase( itr_prev );
	  increasing = false;
	  searching = false;
	} else {
	  A_N.erase( itr_prev );
	}
      } else {
	increasing = false;
      }
    }
    if( searching ){
      searching = ( --itr != begin );
    }
  }
  string answer{};
  itr = A_N.begin();
  while( itr != end ){
    answer += "(" + itr->m_a + "|" + itr->m_b + ")";
    itr++;
  }
  return answer;
}

Veblen Order::VNF( const Veblen& N ) const
{
  string a = VNF( N.m_a );
  string b = VNF( N.m_b );
  list<Veblen> A_b = move( AdditionArray( b ) );
  Veblen N_copy = Veblen( a , b );
  if( A_b.size() != 1 ){
    return N_copy;
  }
  Veblen& b_VNF = A_b.front();
  if( operator()( b_VNF , N_copy ) ){
    return N_copy;
  }
  return b_VNF;
}

int MAIN()
{
  UNTIE;
  CEXPR( int , length , 30 );
  CIN( string , T_0 );
  int size_0 = T_0.size();
  ASSERT( size_0 , 3 , length );
  CIN( string , T_1 );
  int size_1 = T_1.size();
  ASSERT( size_1 , 3 , length );
  Order ord{};
  RETURN( ord( ord.VNF( T_1 ) , ord.VNF( T_0 ) ) ? 0 : 1 );
}
0