結果

問題 No.3582 部分和不等式
コンテスト
ユーザー 👑 p-adic
提出日時 2023-08-22 20:21:00
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,620 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,179 ms
コンパイル使用メモリ 232,264 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2026-07-03 20:53:56
合計ジャッジ時間 41,181 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 乱択解チェック
#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define CERR( MESSAGE ) cerr << MESSAGE << endl;
  #define COUT( ANSWER ) cout << ANSWER << endl
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( MESSAGE ) 
  #define COUT( ANSWER ) cout << ANSWER << "\n"
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAIN main
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_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 AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end()
#define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT

#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif

int MAIN()
{
  UNTIE;
  chrono::system_clock::time_point watch = chrono::system_clock::now();
  CEXPR( int , bound_NQ , 1e3 );
  CIN_ASSERT( N , 1 , bound_NQ );
  CIN_ASSERT( Q , 1 , bound_NQ );
  list<tuple<ll,list<int>,list<int> > > query{};  
  CEXPR( ll , bound_M , 1e9 );
  int temp;
  REPEAT( Q ){
    CIN_ASSERT( A , 0 , N );
    CIN_ASSERT( B , 0 , N );
    CIN_ASSERT( M , -bound_M , bound_M );
    CIN( string , S );
    query.push_back( { move( M ) , {} , {} } );
    auto& q = query.back();
    list<int>& qS = get<1>( q );
    REPEAT( A ){
      CIN_ASSERT( Si , 1 , N );
      qS.push_back( --Si );
    }
    CIN( string , T );
    list<int>& qT = get<2>( q );
    REPEAT( B ){
      CIN_ASSERT( Ti , 1 , N );
      qT.push_back( --Ti );
    }
  }
  int x[bound_NQ];
  int rand_half = RAND_MAX / 2;
  int count = 0;
  while( static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 ) < 1990.0 ){
    count++;
    FOR( i , 0 , N ){
      x[i] = rand() - rand_half;
    }
    bool belong = false;
    FOR_ITR( query ){
      ll diff = -get<0>( *itr );
      auto& qS = get<1>( *itr );
      FOR_ITR( qS ){
	diff += x[*itr];
      }
      auto& qT = get<2>( *itr );
      FOR_ITR( qT ){
	diff -= x[*itr];
      }
      if( diff <= 0 ){
	belong = true;
	break;
      }
    }
    if( !belong ){
      cerr << count << "\n";
      RETURN( "No" );
    }
  }
  cerr << count << "\n";
  RETURN( "Yes" );
}
0