結果

問題 No.2126 MEX Game
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:58:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,485 bytes
コンパイル時間 830 ms
コンパイル使用メモリ 75,376 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 12:59:40
合計ジャッジ時間 2,622 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <map> // Although map is not used, it's a potential alternative if MAX_VAL was very large or unknown

// Define the maximum possible value for elements in A and the value x according to the problem statement.
const int MAX_VAL = 100000; 

int main() {
    // Use fast I/O operations to speed up input reading.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N; // Number of elements in the sequence A
    std::cin >> N;
    
    // Create a frequency array (using std::vector) to store counts of each number from 0 to MAX_VAL.
    // Initialize all counts to 0. The size needs to be MAX_VAL + 1 to cover the index MAX_VAL.
    std::vector<int> counts(MAX_VAL + 1, 0);
    
    // Read the initial sequence A and update the frequency counts.
    for (int i = 0; i < N; ++i) {
        int A_i; // Current element of A
        std::cin >> A_i;
        
        // We only need to consider values within the valid range [0, MAX_VAL] as specified.
        // Values outside this range might exist initially (problem states 0 <= A_i <= 10^5)
        // or be created, but they don't directly affect the MEX value calculation for MEX <= MAX_VAL + 1.
        // More importantly, any element can be changed to a value x where 0 <= x <= 10^5.
        // The game dynamics hinge on counts of values within [0, MAX_VAL].
        if (A_i >= 0 && A_i <= MAX_VAL) {
            // Increment the count for the value A_i.
            // Optimization: Since the condition only depends on whether the count is < 2 or >= 2,
            // we can cap the count at 2. This prevents potentially large counts if N is large
            // and many elements have the same value, although it doesn't change correctness.
             if (counts[A_i] < 2) {
                 counts[A_i]++;
             }
             // The simpler version `counts[A_i]++;` would also work correctly.
        }
    }

    // Find the smallest non-negative integer 'mex' such that its initial count is less than 2.
    // The logic derived is that Sente can guarantee the final MEX is at least X if and only if
    // for all k from 0 to X-1, the initial count of k is at least 2.
    // Therefore, the final MEX under optimal play will be the smallest non-negative integer X
    // for which the initial count is less than 2.
    int mex = 0; 
    
    // Check values 0, 1, 2, ..., up to MAX_VAL.
    while (mex <= MAX_VAL) { 
        // Check if the count of the current integer 'mex' is less than 2 (i.e., 0 or 1).
        if (counts[mex] < 2) {
            // If the count is less than 2, this is the smallest integer for which Sente cannot
            // guarantee its presence with count >= 2 (based on the 1-vs-1 game logic).
            // This 'mex' value is the final MEX of the game.
            break; 
        }
        // If the count is 2 or more, Sente can guarantee its presence against Gote's attacks.
        // We continue to check the next integer.
        mex++; 
    }
    
    // If the loop completes without finding any integer up to MAX_VAL with count < 2,
    // it means all integers from 0 to MAX_VAL have initial counts >= 2.
    // In this case, the smallest integer not satisfying the condition is MAX_VAL + 1.
    // The loop correctly results in `mex = MAX_VAL + 1` in this scenario.
    std::cout << mex << std::endl; // Output the determined final MEX value.
    
    return 0; // Indicate successful execution.
}
0