#862888 (C++17) No.2540 同値性判定

提出ソース

結果

問題	No.2540 同値性判定
ユーザー	👑 p-adic
提出日時	2023-04-25 19:56:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	7,583 bytes
コンパイル時間	4,103 ms
コンパイル使用メモリ	238,560 KB
実行使用メモリ	24,064 KB
最終ジャッジ日時	2024-10-08 06:35:37
合計ジャッジ時間	10,660 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 16,512 KB
testcase_01	AC	8 ms 11,264 KB
testcase_02	AC	8 ms 11,392 KB
testcase_03	AC	6 ms 11,264 KB
testcase_04	AC	7 ms 11,392 KB
testcase_05	AC	8 ms 11,136 KB
testcase_06	AC	7 ms 11,392 KB
testcase_07	AC	7 ms 11,264 KB
testcase_08	AC	7 ms 11,392 KB
testcase_09	AC	7 ms 11,392 KB
testcase_10	AC	7 ms 11,136 KB
testcase_11	AC	7 ms 11,264 KB
testcase_12	AC	7 ms 11,264 KB
testcase_13	AC	8 ms 11,392 KB
testcase_14	AC	74 ms 12,160 KB
testcase_15	AC	712 ms 19,200 KB
testcase_16	TLE	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
evil_00.txt	--	-
evil_01.txt	--	-
evil_02.txt	--	-
evil_03.txt	--	-
evil_04.txt	--	-
evil_05.txt	--	-
evil_06.txt	--	-
evil_07.txt	--	-
evil_08.txt	--	-
evil_09.txt	--	-
evil_10.txt	--	-
evil_11.txt	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

// 動作確認用（愚直解法と更新内容が一致することを確認）
#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include<bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

#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 CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"

template <int N>
class SqrtCalculation
{
public:
  int m_val;
  inline constexpr SqrtCalculation();
};

template <int N> inline constexpr SqrtCalculation<N>::SqrtCalculation() : m_val( 1 ) { int m_val2 = 1; while( ( m_val2 << 2 ) <= N ){ m_val <<= 1; m_val2 <<= 2; } while( m_val2 < N ){ m_val++; m_val2 = m_val * m_val; } }

#define TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION typename T , T m_T(const T&,const T&) , const T& e_T() , typename U , U o_U(const T&,const U&) , int N , int N_sqrt

// （可換とも結合的とも単位的とも限らない）基点付きマグマ(T,m_T:T^2->T,e_T:1->T)と基点が恒等変換に対応するT作用付き集合(U,o_U:T×U->U)と非負整数Nをパラメータとする。
// 配列による初期化O(N)

// 一点取得O(1)

// 一点更新はなし
// o_Uによる一点更新はo_Uによる区間更新で処理する（O(N^{1/2})）
// o_Uによる区間更新O(N^{1/2})
template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION = SqrtCalculation<N>{}.m_val >
class NonCommutativeDualSqrtDecomposition
{

private:
  U m_a[N];
  T m_b[N_sqrt];
  static constexpr int N_d = N / N_sqrt;
  static constexpr int N_m = N_d * N_sqrt;

public:
  static const T& g_e;
  
  inline constexpr NonCommutativeDualSqrtDecomposition( const U ( &a )[N] );
  inline constexpr NonCommutativeDualSqrtDecomposition( U ( &&a )[N] );

  inline constexpr U Get( const int& i ) const;

  inline constexpr void IntervalAct( const int& i_start , const int& i_final , const T& n );
  
};

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> const T& NonCommutativeDualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::g_e = e_T();

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr NonCommutativeDualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::NonCommutativeDualSqrtDecomposition( const U ( &a )[N] ) : m_a() , m_b() { if( m_b[0] != g_e ){ for( int d = 0 ; d < N_d ; d++ ){ m_b[d] = g_e; } } for( int i = 0 ; i < N ; i++ ){ m_a[i] = a[i]; } }
template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr NonCommutativeDualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::NonCommutativeDualSqrtDecomposition( U ( &&a )[N] ) : m_a() , m_b() { swap( m_a , a ); if( m_b[0] != g_e ){ for( int d = 0 ; d < N_d ; d++ ){ m_b[d] = g_e; } } }

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr U NonCommutativeDualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::Get( const int& i ) const { return i < N_m ? o_U( m_b[i/N_sqrt] , m_a[i] ) : m_a[i]; }

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr void NonCommutativeDualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::IntervalAct( const int& i_start , const int& i_final , const T& n )
{

  if( n != g_e ){
  
    const int i_min = max( i_start , 0 );
    const int i_ulim = min( i_final + 1 , N );
    const int d_0 = ( i_min + N_sqrt - 1 ) / N_sqrt;
    const int d_1 = max( d_0 , i_ulim / N_sqrt );
    const int d_0_N_sqrt = d_0 * N_sqrt ;
    const int i_0 = min( d_0_N_sqrt , i_ulim ) ;
    const int d_1_N_sqrt = d_1 * N_sqrt ;
    const int i_1 = max( i_0 , d_1_N_sqrt );

    if( d_0 > 0 ){

      T& m_bd = m_b[d_0-1];

      if( m_bd != g_e ){
    
	for( int i = d_0_N_sqrt - N_sqrt ; i < d_0_N_sqrt ; i++ ){

	  U& m_ai = m_a[i];
	  m_ai = o_U( m_bd , m_ai );

	}

	m_bd = g_e;

      }
    
    }
  
    for( int i = i_min ; i < i_0 ; i++ ){

      U& m_ai = m_a[i];
      m_ai = o_U( n , m_ai );

    }
  
    for( int d = d_0 ; d < d_1 ; d++ ){

      T& m_bd = m_b[d];
      m_bd = m_T( n , m_bd );

    }

    if( d_1 < N_d ){

      T& m_bd = m_b[d_1];
    
      if( m_bd != g_e ){
      
	for( int i = d_1_N_sqrt + N_sqrt - 1 ; i >= d_1_N_sqrt ; i-- ){

	  U& m_ai = m_a[i];
	  m_ai = o_U( m_bd , m_ai );

	}

	m_bd = g_e;

      }
    
    }
    
    for( int i = i_1 ; i < i_ulim ; i++ ){

      U& m_ai = m_a[i];
      m_ai = o_U( n , m_ai );

    }

  }

  return;
  
}

class M
{
public:
  ull m_a;
  ull m_b;
  bool m_neg;
  constexpr M( const ull& a = -1 , const ull& b = 0 , const bool& neg = false ) : m_a( a ) , m_b( b ) , m_neg( neg ) {}
};

inline M prod( const M& m0 , const M& m1 ) { return  m0.m_neg ? M( ( ~m1.m_b ) & m0.m_a , ( ( ~m1.m_a ) & ( ( ~m1.m_b ) & m0.m_a ) ) | m0.m_b , !m1.m_neg ) : M( m1.m_a & m0.m_a , ( m1.m_b & m0.m_a ) | m0.m_b , m1.m_neg ); }
inline const M& unit() { static const M m{}; return m; }
inline ull act( const M& m , const ull& n ) { return ( ( m.m_neg ? ~n : n ) & m.m_a ) | m.m_b; }
inline bool operator==( const M& m0 , const M& m1 ) { return m0.m_a == m1.m_a && m0.m_b == m1.m_b && m0.m_neg == m1.m_neg; }
inline bool operator!=( const M& m0 , const M& m1 ) { return !( m0 == m1 ); }

inline CEXPR( int , c , 6 );

class Variable
{
public:
  ull m_val[c];
  constexpr Variable() : m_val() { FOR( i , 0 , c ){ ull one{ 1 }; ull& m_val_i = m_val[i]; FOR( d , 0 , 64 ){ if( ( ( d >> i ) & 1 ) == 1 ){ m_val_i += one << d; } } } }
};

int MAIN()
{
  UNTIE;
  CEXPR( int , bound_N , 1000000 );
  CIN_ASSERT( N , 1 , bound_N );
  CEXPR( int , bound_Q , 100000 );
  CIN_ASSERT( Q , 1 , bound_Q );
  constexpr Variable P{};
  static ull X_check[bound_N] = {};
  FOR( i , 0 ,  N ){
    X_check[i] = P.m_val[i % c];
  }
  static NonCommutativeDualSqrtDecomposition<M,prod,unit,ull,act,bound_N> X{ X_check };
  string land = "land";
  string lor = "lor";
  string Rightarrow = "Rightarrow";
  string Yes = "Yes";
  string No = "No";
  N--;
  REPEAT( Q ){
    CIN_ASSERT( h , 0 , N );
    CIN( string , o );
    CIN_ASSERT( l0 , 0 , N );
    CIN_ASSERT( r0 , l0 , N );
    CIN_ASSERT( l1 , 0 , N );
    CIN_ASSERT( r1 , l1 , N );
    ull Y = X_check[h];
    if( o == land ){
      X.IntervalAct( l0 , r0 , M( Y ) );
      FOREQ( i , l0 , r0 ){
	assert( X.Get( i ) == ( X_check[i] &= Y ) );
      }
    } else if( o == lor ){
      X.IntervalAct( l0 , r0 , M( -1 , Y ) );
      FOREQ( i , l0 , r0 ){
	assert( X.Get( i ) == ( X_check[i] |= Y ) );
      }
    } else {
      assert( o == Rightarrow );
      X.IntervalAct( l0 , r0 , M( -1 , Y , true ) );
      FOREQ( i , l0 , r0 ){
	assert( X.Get( i ) == ( ( X_check[i] ^= -1 ) |= Y ) );
      }
    }
    set<ull> X_interval{};
    bool found = false;
    FOREQ( i , l1 , r1 ){
      ull Xi = X.Get( i );
      assert( Xi == X_check[i] );
      if( X_interval.count( Xi ) == 0 ){
	X_interval.insert( Xi );
      } else {
	found = true;
	break;
      }
    }
    COUT( found ? Yes : No );
  }
  QUIT;
}

yukicoder

結果

テストケース

ソースコード