#1083828 (C++17) No.1888 Odd Insertion

• 問題: No.1888 Odd Insertion
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:04:08
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 6,269 bytes
• コンパイル時間: 710 ms
• コンパイル使用メモリ: 87,568 KB
• 実行使用メモリ: 18,976 KB
• 最終ジャッジ日時: 2025-05-14 13:05:59
• 合計ジャッジ時間: 8,887 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 14 WA * 10 TLE * 1 -- * 12

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <set>
#include <list>
#include <algorithm>
#include <iterator> // Required for std::advance

int main() {
    // Faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N;
    std::cin >> N;
    
    // Use std::list to represent the sequence A. 
    // std::list allows O(1) deletion time complexity given an iterator.
    std::list<int> A;
    for (int k = 0; k < N; ++k) {
        int p_k;
        std::cin >> p_k;
        A.push_back(p_k);
    }
    
    // Use std::set to represent the set S of available numbers.
    // Initially, S contains elements that have been "removed" from A in the reverse process.
    // At the end of the reverse process, S should contain {1, ..., N}.
    // std::set allows efficient O(log N) insertion and retrieval of minimum elements.
    std::set<int> S; 
    
    // Store the sequence of operations (x_i, y_i) derived from the reverse process.
    // ops[i-1] will store the operation performed at step i in the forward process.
    std::vector<std::pair<int, int>> ops(N);
    
    // Perform the process in reverse, from step i = N down to 1.
    for (int i = N; i >= 1; --i) {
        // Determine the condition value m2.
        // The element x_i removed at step i must satisfy:
        // x_i is the smallest or second smallest element in the set S U {x_i}.
        // Let S_after = S (the set after adding x_i) and S_before = S U {x_i}.
        // Let m1', m2' be the first two minimums of S_before. Condition: x_i = m1' or x_i = m2'.
        // Let m1, m2 be the first two minimums of S_after (current S).
        // The condition is equivalent to x_i <= m2 (where m2 = infinity if |S| < 2).
        // We use N+2 as a proxy for infinity, as all values are <= N.
        int m2 = N + 2; 
        if (S.size() >= 2) {
             auto it = S.begin();
             ++it; // Move iterator to the second element
             m2 = *it; // Assign the second minimum value to m2
        }
        // If S.size() is 0 or 1, m2 remains N+2. This correctly reflects that any x_i satisfies the condition
        // because either x_i is the smallest element or there's at most one element smaller than it in S U {x_i}.

        int best_y = -1; // Stores the chosen odd index y_i for step i. Initialize to -1 (invalid).
        std::list<int>::iterator best_it; // Stores the iterator pointing to the element A[best_y]

        // Determine the largest odd index k such that 1 <= k <= i.
        int k = (i % 2 == 1) ? i : i - 1; 
        // Check if k is valid. Since N >= 1, i >= 1, k will always be >= 1.
        if (k < 1) {
            // This case should technically not happen for N >= 1.
            // Added for robustness, though maybe unnecessary.
             if (i >= 1) k = 1; 
             else continue; // If somehow i becomes 0
        }
        
        // Check if A is empty. A should have size i at the start of reverse step i.
        // If A is empty and i >= 1, it means the target permutation P was impossible to form.
        if (A.empty()) {
             if (i >= 1) {
                 std::cout << "No" << std::endl; 
                 return 0;
             } else { // If i=0, A should be empty, loop is finished.
                 continue;
             }
        }

        // Check if calculated index k is valid with respect to current list size.
        // List A size should be exactly i. k is always <= i.
        if (k > (int)A.size()) {
            // This indicates an internal logic error or an impossible state has been reached.
             std::cout << "No" << std::endl; 
             return 0;
        }

        // Find an iterator pointing to the element at 1-based index k in list A.
        // std::advance takes O(k) time for std::list.
        auto it_k = A.begin();
        std::advance(it_k, k - 1); 
        
        // Iterate through odd indices y in decreasing order, from k down to 1.
        // We are looking for the largest odd index y such that A[y] satisfies the condition A[y] <= m2.
        for (int y = k; y >= 1; y -= 2) {
             int val = *it_k; // Get the value at the current position (index y).
             if (val <= m2) { // Check if the condition is met.
                 best_y = y;    // Store the index y.
                 best_it = it_k; // Store the iterator.
                 break; // Found the largest valid y, exit the loop.
             }
            
             // If condition not met and y > 1, move the iterator back 2 positions
             // to check the next smaller odd index (y-2).
             if (y > 1) {
                 // Moving back twice is safe for bidirectional iterators like std::list::iterator
                 // as long as we are not already at the beginning. Since y > 1, we are checking
                 // index y-2, which is >= -1. The check ensures y >= 3 when moving back.
                 // The iterator initially points to index k-1 >= 0. Moving back twice from index y-1 (>=2)
                 // reaches index y-3 >= 0. So this is safe.
                 --it_k;
                 --it_k;
             }
        }

        // If no valid odd index y was found (best_y remains -1),
        // it means the target permutation P cannot be formed.
        if (best_y == -1) {
            std::cout << "No" << std::endl;
            return 0; 
        }
        
        // A valid pair (x_i, y_i) is found using the element A[best_y].
        int x_i = *best_it; // The value removed is x_i.
        A.erase(best_it);   // Remove the element from list A. O(1) time complexity.
        S.insert(x_i);      // Add x_i to the set S. O(log N) time complexity.
        ops[i-1] = {x_i, best_y}; // Store the operation (x_i, y_i) for the forward step i.
                                  // Store in ops[i-1] because vector is 0-indexed.
    }

    // If the loop completes successfully for all i from N down to 1,
    // it means a valid sequence of operations exists.
    std::cout << "Yes" << std::endl;
    for (int i = 0; i < N; ++i) {
        // Output the recorded operations in forward order (i=1 to N).
        std::cout << ops[i].first << " " << ops[i].second << "\n";
    }

    return 0;
}