結果
| 問題 |
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;
}