結果
| 問題 | No.2165 Let's Play Nim! |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-12-16 00:49:25 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,182 bytes |
| コンパイル時間 | 3,283 ms |
| コンパイル使用メモリ | 220,796 KB |
| 実行使用メモリ | 25,580 KB |
| 平均クエリ数 | 3.05 |
| 最終ジャッジ日時 | 2024-11-14 17:09:50 |
| 合計ジャッジ時間 | 7,680 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 26 ms
25,452 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | AC | 23 ms
24,812 KB |
| testcase_31 | AC | 24 ms
24,812 KB |
| testcase_32 | WA | - |
| evil_2_big_1.txt | WA | - |
| evil_2_big_2.txt | WA | - |
| evil_2_big_3.txt | WA | - |
| evil_big_1.txt | WA | - |
| evil_big_2.txt | WA | - |
| evil_big_3.txt | WA | - |
ソースコード
// #define _GLIBCXX_DEBUG
#pragma GCC optimize ( "O3" )
#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
#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( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#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 FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
// #define COUT( ANSWER ) cout << ( ANSWER ) << "\n";
#define COUT( ANSWER ) cout << ( ANSWER ) << endl;
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ARGUMENT ) % MODULO ) % MODULO; \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , MAX_I , LENGTH , MODULO ) \
ll ANSWER[LENGTH]; \
ll ANSWER_INV[LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_I ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
} \
POWER_MOD( FACTORIAL_MAX_INV , ANSWER[MAX_I] , MODULO - 2 , MODULO ); \
ANSWER_INV[MAX_I] = FACTORIAL_MAX_INV; \
FOREQINV( i , MAX_I - 1 , 0 ){ \
ANSWER_INV[i] = ( FACTORIAL_MAX_INV *= i + 1 ) %= MODULO; \
} \
} \
\
// 通常の二分探索
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MAXIMUM; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
while( VARIABLE_FOR_BINARY_SEARCH_L != ANSWER ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
} \
\
// 二進法の二分探索
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MINIMUM; \
{ \
ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 = 1; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 *= 2; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \
ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 != 0 ){ \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2; \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
break; \
} else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \
} \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2; \
} \
\
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; }
int main()
{
CEXPR( int , bound , 75000 );
CIN_ASSERT( N , 1 , bound );
int A[bound+1];
int sum = 0;
set<int> I{};
FOREQ( i , 1 , N ){
CIN_ASSERT( Ai , 1 , bound );
A[i] = Ai;
sum ^= Ai;
I.insert( i );
}
int t = sum == 0 ? 0 : 1;
COUT( t );
int Ai_next;
int diff_max;
int i_diff_max;
while( ! I.empty() ){
if( t == 0 ){
CIN_ASSERT( i , 1 , N );
assert( I.count( i ) == 1 );
int& Ai = A[i];
CIN_ASSERT( k , 1 , Ai );
if( Ai == k ){
sum = Ai;
I.erase( i );
} else {
Ai -= k;
sum = k;
}
} else {
diff_max = 0;
FOR_ITR( I , itr , end ){
const int& i = *itr;
int& Ai = A[i];
Ai_next = Ai ^ sum;
if( diff_max < Ai - Ai_next ){
if( Ai == sum ){
cout << i << " " << Ai << endl;
I.erase( i );
diff_max = 0;
break;
} else {
diff_max = Ai - Ai_next;
i_diff_max = i;
}
}
}
if( diff_max != 0 ){
cout << i_diff_max << " " << diff_max << endl;
A[i_diff_max] ^= sum;
}
}
CIN_ASSERT( ret , -1 , 0 );
if( ret == -1 ){
QUIT;
}
t = 1 - t;
}
QUIT;
}