結果

問題 No.2397 ω冪
ユーザー 👑 p-adicp-adic
提出日時 2022-11-17 14:25:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 3,212 bytes
コンパイル時間 2,457 ms
コンパイル使用メモリ 210,152 KB
実行使用メモリ 6,812 KB
最終ジャッジ日時 2023-10-19 07:08:55
合計ジャッジ時間 4,381 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
4,348 KB
testcase_01 AC 3 ms
4,348 KB
testcase_02 AC 3 ms
4,348 KB
testcase_03 AC 3 ms
4,348 KB
testcase_04 AC 3 ms
4,348 KB
testcase_05 AC 3 ms
4,348 KB
testcase_06 AC 4 ms
4,348 KB
testcase_07 AC 3 ms
4,348 KB
testcase_08 AC 3 ms
4,348 KB
testcase_09 AC 3 ms
4,348 KB
testcase_10 AC 3 ms
4,348 KB
testcase_11 AC 3 ms
4,348 KB
testcase_12 AC 4 ms
4,348 KB
testcase_13 AC 4 ms
4,348 KB
testcase_14 AC 3 ms
4,348 KB
testcase_15 AC 4 ms
4,348 KB
testcase_16 AC 4 ms
4,348 KB
testcase_17 AC 4 ms
4,348 KB
testcase_18 AC 3 ms
4,348 KB
testcase_19 AC 3 ms
4,348 KB
testcase_20 AC 4 ms
4,348 KB
testcase_21 AC 4 ms
4,348 KB
testcase_22 AC 4 ms
4,348 KB
testcase_23 AC 2 ms
4,348 KB
testcase_24 AC 3 ms
4,348 KB
testcase_25 AC 3 ms
4,348 KB
testcase_26 AC 3 ms
4,348 KB
testcase_27 AC 3 ms
4,348 KB
testcase_28 AC 3 ms
4,348 KB
testcase_29 AC 3 ms
4,348 KB
testcase_30 AC 3 ms
4,348 KB
testcase_31 AC 3 ms
4,348 KB
testcase_32 AC 3 ms
4,348 KB
testcase_33 AC 3 ms
4,348 KB
testcase_34 AC 3 ms
4,348 KB
testcase_35 AC 4 ms
4,348 KB
testcase_36 AC 38 ms
5,240 KB
testcase_37 AC 37 ms
5,260 KB
testcase_38 AC 38 ms
5,256 KB
testcase_39 AC 39 ms
5,272 KB
testcase_40 AC 110 ms
6,812 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
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 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 

inline CEXPR( int , log_length , 17 );

class Order
{
public:
  inline Order() = default;
  template <int L> list<bitset<log_length> > A( const bitset<L>& N ) const;
  template <int L> bool operator()( const bitset<L>& N , const bitset<L>& M ) const;
  template <int L> bitset<L> CNF( const bitset<L>& N ) const;
};

template <int L>
list<bitset<log_length> > Order::A( const bitset<L>& N ) const
{
  list<bitset<log_length> > S{};
  int i_prev = 0;
  FOR( i , 0 , L ){
    if( N[i] == 1 ){
      S.push_front( bitset<log_length>( i - i_prev ) );
      i_prev = i + 1;
    }
  }
  return S;
}

template <int L>
bool Order::operator()( const bitset<L>& N , const bitset<L>& M ) const
{
  list<bitset<log_length> > A_N = move( A<L>( N ) );
  list<bitset<log_length> > A_M = move( A<L>( 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 ){
    bitset<log_length>& Ni = *itr_N;
    bitset<log_length>& Mi = *itr_M;
    if( operator()<log_length>( Ni , Mi ) ){
      return true;
    } else if( Ni != Mi ){
      return false;
    }
    itr_N++;
    itr_M++;
  }
  return itr_M != end_M;
}

template <int L>
bitset<L> Order::CNF( const bitset<L>& N ) const
{
  list<bitset<log_length> > A_N = move( A<L>( N ) );
  auto begin = A_N.begin();
  auto end = A_N.end();
  if( begin == end ){
    return bitset<L>( 0 );
  }
  auto itr = begin;
  auto itr_prev = itr;
  {
    bitset<log_length>& A_N_i = *itr;
    A_N_i = move( CNF<log_length>( A_N_i ) );
    itr++;
  }
  while( itr != end ){
    bitset<log_length>& A_N_i = *itr;
    A_N_i = move( CNF<log_length>( A_N_i ) );
    itr_prev++;
    itr++;
  }
  itr = itr_prev;
  bool searching = ( itr != begin );
  while( searching ){
    bitset<log_length>& A_N_i = *itr;
    bool increasing = true;
    while( increasing ){
      itr_prev = itr;
      itr_prev--;
      bitset<log_length>& A_N_i_prev = *itr_prev;
      if( operator()<log_length>( 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 );
    }
  }
  bitset<L> answer{ 0 };
  itr = A_N.begin();
  while( itr != end ){
    answer <<= 1;
    answer[0] = 1;
    answer <<= itr->to_ullong();
    itr++;
  }
  return answer;
}

int MAIN()
{
  UNTIE;
  CEXPR( int , length , 100000 );
  CIN( bitset<length> , N );
  CIN( bitset<length> , M );
  Order ord{};
  RETURN( ord.operator()<length>( ord.CNF<length>( N ) , ord.CNF<length>( M ) ) ? "Yes" : "No" );
}
0