結果
| 問題 |
No.1379 Postponed
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,544 bytes |
| コンパイル時間 | 1,147 ms |
| コンパイル使用メモリ | 88,868 KB |
| 実行使用メモリ | 742,368 KB |
| 最終ジャッジ日時 | 2025-05-14 13:02:17 |
| 合計ジャッジ時間 | 7,094 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 MLE * 1 |
| other | AC * 40 TLE * 1 -- * 23 |
ソースコード
#include <iostream> // For standard input/output operations
#include <vector> // For using std::vector to represent sequences
#include <map> // For using std::map to detect cycles by storing visited states
#include <numeric> // Included for completeness, not strictly used in the final code
/**
* @brief Computes the next state A^(t) based on the current state A^(t-1).
*
* According to the problem description, the sequence A^(t) is obtained from A^(t-1)
* by cyclically shifting the first A^(t-1)_1 + 1 elements one position to the left.
* Let A^(t-1) be represented by the vector `current_A`. Let N be its size.
* Let x = current_A[0] (using 0-based indexing for the first element).
* The transformation applies to the prefix of length x+1, i.e., indices 0 to x.
* The elements (current_A[0], current_A[1], ..., current_A[x]) become
* (current_A[1], current_A[2], ..., current_A[x], current_A[0]).
* The elements from index x+1 to N-1 remain unchanged.
*
* @param current_A A constant reference to the vector representing the current state A^(t-1).
* @return A new vector representing the next state A^(t).
*/
std::vector<int> compute_next_state(const std::vector<int>& current_A) {
int N = current_A.size(); // Get the length of the sequence.
// Handle the edge case of an empty sequence. Based on problem constraints (N >= 2), this shouldn't happen.
if (N == 0) return {};
// Get the value of the first element, A^(t-1)_1. In 0-based indexing, this is current_A[0].
// This value determines how many elements are involved in the cyclic shift. Let's call it `x`.
int x = current_A[0];
// Problem constraints state 1 <= A[i] <= N-1 for all i. Thus, 1 <= x <= N-1.
// This implies x >= 1, so the number of elements to shift, x+1, is at least 2.
// Also, x <= N-1 implies x+1 <= N, meaning the indices involved (0 to x) are within the bounds of the vector.
// Create a copy of the current state. We will modify this copy to generate the next state.
std::vector<int> next_A = current_A;
// Perform the cyclic shift left operation on the prefix of length x+1 (indices 0 to x).
// This operation is only meaningful if x >= 1 (i.e., at least 2 elements are involved).
// Since constraints guarantee x >= 1, we always perform a shift.
// Save the value of the first element (at index 0) before it gets overwritten.
int first_val = next_A[0];
// Shift elements from index 1 up to x one position to the left.
// The element originally at index i+1 moves to index i.
for (int i = 0; i < x; ++i) {
next_A[i] = next_A[i+1];
}
// Place the saved first element's value into the last position of the shifted segment (index x).
next_A[x] = first_val;
// Elements from index x+1 to N-1 remain unchanged because we started with a copy `next_A = current_A`.
// Return the computed next state vector.
return next_A;
}
int main() {
// Optimize standard C++ I/O operations for faster execution.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Variable to store the length of the sequence.
long long K; // Variable to store the number of steps (can be very large).
std::cin >> N >> K; // Read N and K from standard input.
// Declare a vector `A` to store the current state of the sequence.
// Initialize its size to N.
std::vector<int> A(N);
// Read the initial sequence A^(0) from standard input.
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
// `history` is a vector of vectors, storing the sequence of states encountered: A^(0), A^(1), ..., A^(t).
// This allows retrieving state A^(idx) using `history[idx]` in O(N) time (to copy) or O(1) access time if passed by reference.
std::vector<std::vector<int>> history;
// `visited` is a map where keys are states (std::vector<int>) and values are the time steps (long long)
// at which each state was first encountered. This is used for cycle detection.
// std::map uses balanced binary search trees, giving logarithmic time complexity for lookups, insertions, and deletions.
// It automatically handles comparisons for std::vector<int>.
std::map<std::vector<int>, long long> visited;
// Initialize the process:
// The state at time t=0 is the input sequence `A`.
history.push_back(A); // Add A^(0) to the history log.
visited[A] = 0; // Record that state A was first seen at time step 0.
// Simulate the process step-by-step from t=1 up to K steps.
for (long long t = 1; t <= K; ++t) {
// Compute the next state A^(t) based on the current state A^(t-1) (which is stored in variable `A`).
A = compute_next_state(A);
// Check if the newly computed state `A` (representing A^(t)) has been encountered before.
// We use map's `find` method for this check.
auto it = visited.find(A);
if (it != visited.end()) {
// Cycle detected! The current state `A` has been seen before.
long long p = it->second; // `p` is the time step when this state `A` was first encountered.
// This marks the beginning of the cycle. States are A^(p), A^(p+1), ...
long long L = t - p; // `L` is the length of the cycle (number of states in the cycle).
// The cycle consists of states A^(p), ..., A^(t-1).
// We need to determine the state A^(K). Since K >= t, and the sequence is periodic with period L after step p,
// the state A^(K) is equivalent to the state at step p + (K-p) mod L.
// Calculate the index in the `history` vector that corresponds to this target time step.
long long final_idx = p + (K - p) % L;
// Retrieve the final state A^(K) from the `history` using the calculated index.
A = history[final_idx];
// Print the final state A^(K). Elements should be space-separated.
for (int i = 0; i < N; ++i) {
std::cout << A[i] << (i == N - 1 ? "" : " "); // Print space except after the last element.
}
std::cout << std::endl; // Print a newline character at the end.
// Terminate the program successfully as we have found and printed the answer.
return 0;
} else {
// The state `A` (representing A^(t)) is encountered for the first time at step `t`.
// We need to record this new state and its time step.
history.push_back(A); // Add the new state A^(t) to the history log.
visited[A] = t; // Mark state A as visited at time step t in the map.
// The variable `A` already holds the state A^(t), ready for the computation of A^(t+1) in the next iteration.
}
}
// If the loop completes all K iterations without returning, it means K was reached before
// a cycle relevant to K was detected (e.g., K is smaller than the preperiod length p, or K < p+L).
// In this case, the variable `A` holds the final state A^(K).
// Print the final state A^(K).
for (int i = 0; i < N; ++i) {
std::cout << A[i] << (i == N - 1 ? "" : " "); // Print space except after the last element.
}
std::cout << std::endl; // Print a newline character at the end.
return 0; // Indicate successful execution of the program.
}