結果

問題 No.2308 [Cherry 5th Tune B] もしかして、真?
ユーザー 👑 p-adicp-adic
提出日時 2023-05-06 17:21:20
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 87 ms / 2,000 ms
コード長 8,668 bytes
コンパイル時間 2,797 ms
コンパイル使用メモリ 107,060 KB
最終ジャッジ日時 2025-02-12 20:35:19
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
#include <vector>
using namespace std;
using ll = long long;
using uint = unsigned int;
#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 GETLINE( S ) string S; getline( cin , S )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; 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"
// InitialSegmentSumuintint
// 使
// T& T::operator=( const T& )
// T& T::operator+=( const T& )
// T operator-( const T& , const T& )IntervalSum
// T operator<( const T& , const T& )BinarySearch
template <typename T>
class BIT
{
private:
int m_N;
vector<T> m_fenwick;
int m_power;
public:
inline BIT( const int& N );
inline void Set( const int& i , const T& n );
void Add( const int& i , const T& n );
T InitialSegmentSum( const int& i_final ) const;
inline T IntervalSum( const int& i_start , const int& i_final ) const;
// operator+=T()
// InitialSegmentSum( i )ti2
int BinarySearch( const T& t ) const;
};
template <typename T> inline BIT<T>::BIT( const int& N ) : m_N( N ) , m_fenwick( N + 1 ) , m_power( 1 )
{
// 1
for( int j = 1 ; j <= N ; j++ ){
T& fenwick_j = m_fenwick[j] = 1;
int i = j - 1;
int i_lim = j - ( j & -j );
while( i != i_lim ){
fenwick_j += m_fenwick[i];
i -= ( i & -i );
}
}
while( m_power < N ){
m_power <<= 1;
}
}
template <typename T> inline void BIT<T>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); }
template <typename T>
void BIT<T>::Add( const int& i , const T& n )
{
int j = i + 1;
while( j <= m_N ){
m_fenwick[j] += n;
j += ( j & -j );
}
return;
}
template <typename T>
T BIT<T>::InitialSegmentSum( const int& i_final ) const
{
T sum = 0;
int j = ( i_final < m_N ? i_final : m_N - 1 ) + 1;
while( j > 0 ){
sum += m_fenwick[j];
j -= j & -j;
}
return sum;
}
template <typename T> inline T BIT<T>::IntervalSum( const int& i_start , const int& i_final ) const { return InitialSegmentSum( i_final ) -
    InitialSegmentSum( i_start - 1 ); }
template <typename T> inline int BIT<T>::BinarySearch( const T& t ) const
{
int j = 0;
int power = m_power;
T sum{};
T sum_next{};
while( power > 0 ){
int j_next = j | power;
if( j_next < m_N ){
sum_next += m_fenwick[j_next];
if( sum_next < t ){
sum = sum_next;
j = j_next;
} else {
sum_next = sum;
}
}
power >>= 1;
}
// InitialSegmentSum( i )tij1
// InitialSegmentSum( i )tij=0
// jInitialSegmentSum( i )ti
return j;
}
//
// 1
#define GETLINE_COUNT( S , VARIABLE_NUMBER ) GETLINE( S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S = 0; int VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_
    ## S = S.size(); { int size = S.size(); int count = 0; for( int i = 0 ; i < size ; i++ ){ if( S.substr( i , 1 ) == " " ){ count++; } } assert(
    count + 1 == VARIABLE_NUMBER ); }
//
#define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert(
    VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
// #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; getline( cin , VARIABLE_FOR_CHECK_REDUNDANT_INPUT ); assert(
    VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
// |N| <= BOUNDNS
#define STOI( S , N , BOUND ) TYPE_OF( BOUND ) N = 0; { bool VARIABLE_FOR_POSITIVITY_FOR_GETLINE = true; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_
    ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); if( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) == "-" ){
    VARIABLE_FOR_POSITIVITY_FOR_GETLINE = false; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S <
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); } assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != " " ); string
    VARIABLE_FOR_LETTER_FOR_GETLINE{}; int VARIABLE_FOR_DIGIT_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S <
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != " " :
    false ){ VARIABLE_FOR_DIGIT_FOR_GETLINE = stoi( VARIABLE_FOR_LETTER_FOR_GETLINE ); assert( N < BOUND / 10 ? true : N == BOUND / 10 &&
    VARIABLE_FOR_DIGIT_FOR_GETLINE <= BOUND % 10 ); N = N * 10 + VARIABLE_FOR_DIGIT_FOR_GETLINE; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } if( !
    VARIABLE_FOR_POSITIVITY_FOR_GETLINE ){ N *= -1; } if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){
    VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }
// SSEPARATORT
#define SEPARATE( S , T , SEPARATOR ) string T{}; { assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); int
    VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev = VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S; assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_
    ## S , 1 ) != SEPARATOR ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S <
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) !=
    SEPARATOR : false ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } T = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev ,
    VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S - VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev ); if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S <
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }
int main()
{
UNTIE;
CEXPR( int , bound_T , 100000 );
CIN_ASSERT( T , 1 , bound_T );
CEXPR( int , bound_N_sum , 200000 );
int N_rest = bound_N_sum;
string True = "True";
string False = "False";
CEXPR( int , op_length , 4 );
string op[op_length] = { "and" , "or" , "xor" , "imp" };
bool X[bound_N_sum];
int Y[bound_N_sum];
REPEAT( T ){
CIN_ASSERT( N , 2 , N_rest );
N_rest -= N;
FOR( i , 0 , N ){
CIN( string , Xi );
X[i] = Xi == True ? true : ( assert( Xi == False ) , false );
}
int N_minus = N - 1;
FOR( i , 0 , N_minus ){
CIN( string , Yi );
bool found = false;
FOR( j , 0 , op_length ){
if( Yi == op[j] ){
Y[i] = j;
found = true;
break;
}
}
assert( found );
}
// A_ii < N
BIT<int> Kaiser{ N };
FOR( j , 0 , N_minus ){
CIN_ASSERT( Si , 1 , N - j );
// Si+1n
int n = Kaiser.BinarySearch( Si + 1 );
// Sin_prev
int n_prev = Kaiser.BinarySearch( Si );
Kaiser.Add( n , -1 );
int& Yn = Y[n - 1];
X[n_prev] =
Yn == 0 ? ( X[n_prev] && X[n] ) :
Yn == 1 ? ( X[n_prev] || X[n] ) :
Yn == 2 ? ( X[n_prev] != X[n] ) :
( ( !X[n_prev] ) || X[n] );
}
COUT( X[0] ? True : False );
}
CHECK_REDUNDANT_INPUT;
QUIT;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0