結果
| 問題 |
No.1425 Yet Another Cyclic Shifts Sorting
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 50 ms / 2,000 ms |
| コード長 | 10,755 bytes |
| コンパイル時間 | 966 ms |
| コンパイル使用メモリ | 84,000 KB |
| 実行使用メモリ | 14,080 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:42 |
| 合計ジャッジ時間 | 3,565 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 48 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // Not strictly needed for this solution, but included for completeness
// KMP preprocessing function to compute the failure function (LPS array).
// The LPS array `lps` for a pattern `p` stores at index `i` the length of the
// longest proper prefix of `p[0..i]` that is also a suffix of `p[0..i]`.
// A proper prefix is not the whole string itself.
// Takes a constant reference to a vector of long long representing the pattern.
std::vector<int> compute_lps(const std::vector<long long>& pattern) {
int m = pattern.size();
// Handle empty pattern case - returns an empty vector.
if (m == 0) return {};
std::vector<int> lps(m, 0); // Initialize LPS array with 0s. lps[0] is always 0.
int length = 0; // `length` stores the length of the previous longest prefix suffix.
int i = 1; // Start computing `lps` from the second character (index 1).
while (i < m) {
// If the current character `pattern[i]` matches the character after the current `length`,
// it means we can extend the current longest prefix suffix.
if (pattern[i] == pattern[length]) {
length++; // Increment the length.
lps[i] = length; // Store the new length in lps[i].
i++; // Move to the next character in the pattern.
} else {
// If characters do not match...
if (length != 0) {
// ...and we had a non-zero length prefix suffix (`length > 0`),
// we need to find the next shorter possible prefix suffix.
// The length of this shorter prefix suffix is given by `lps[length - 1]`.
// We update `length` to this value and retry the comparison `pattern[i] == pattern[length]`
// in the next iteration without incrementing `i`.
length = lps[length - 1];
} else {
// ...and `length` is 0, it means `pattern[i]` does not even match `pattern[0]`.
// So, the longest prefix suffix ending at index `i` has length 0.
lps[i] = 0;
i++; // Move to the next character in the pattern.
}
}
}
return lps; // Return the computed LPS array.
}
// KMP search function to check if the `pattern` exists as a contiguous substring within the `text`.
// Returns true if found, false otherwise.
// Takes constant references to two vectors of long long: `text` and `pattern`.
bool kmp_search(const std::vector<long long>& text, const std::vector<long long>& pattern) {
int n = text.size(); // Length of the text.
int m = pattern.size(); // Length of the pattern.
// Handle edge cases:
if (m == 0) return true; // An empty pattern is considered found in any text.
if (n < m) return false; // Pattern cannot be found if it's longer than the text.
if (n == 0) return false; // Non-empty pattern cannot be found in empty text. (Empty pattern handled above).
// Compute the LPS array for the pattern, which helps optimize shifts on mismatches.
std::vector<int> lps = compute_lps(pattern);
int i = 0; // index for text.
int j = 0; // index for pattern.
while (i < n) {
// If the current characters match, advance both indices.
if (pattern[j] == text[i]) {
i++;
j++;
}
// Check if we have matched the entire pattern.
if (j == m) {
// Pattern found starting at index `i - m` in the text.
return true;
// If we needed to find all occurrences, we would reset `j` using the LPS array:
// j = lps[j - 1];
// And continue the search from the current `i`.
}
// If a mismatch occurs after `j` characters have matched (`j > 0`),
// or if the first characters mismatch (`j == 0`).
else if (i < n && pattern[j] != text[i]) {
// If `j` is not 0, it means we had some partial match.
// We use the LPS array value `lps[j - 1]` to find the length of the longest proper prefix
// of `pattern[0..j-1]` that is also a suffix. This length becomes the new `j`.
// This effectively shifts the pattern forward while reusing known matched suffixes.
if (j != 0) {
j = lps[j - 1];
} else {
// If `j` is 0, the mismatch occurred at the very first character of the pattern.
// We cannot shift based on prefixes, so we simply advance the text index `i`.
i++;
}
}
}
// If we reach the end of the text without finding the complete pattern.
return false;
}
// Function to check if vector `p` is a cyclic shift of vector `b`.
// Both vectors `p` and `b` are expected to have the same size `L >= 0`.
bool is_cyclic_shift(const std::vector<long long>& p, const std::vector<long long>& b) {
// Check if the sizes are equal. If not, they cannot be cyclic shifts.
if (p.size() != b.size()) {
return false;
}
int L = p.size(); // Get the common size.
// Handle the trivial case of empty vectors. They are considered cyclic shifts of each other.
if (L == 0) {
return true;
}
// Optimization: If `p` and `b` are identical, `p` is a cyclic shift of `b` (with a shift of 0).
// This comparison takes O(L) time.
if (p == b) {
return true;
}
// To check for cyclic shifts efficiently, we use the KMP algorithm.
// The idea is that `p` is a cyclic shift of `b` if and only if `p` is a substring of `b` concatenated with itself (minus one character).
// Construct the search text `T = b + b[0...L-2]`. `T` contains all cyclic shifts of `b` as substrings.
// For example, if b = [1, 2, 3], L=3. T = [1, 2, 3] + [1, 2] = [1, 2, 3, 1, 2].
// The cyclic shifts [1, 2, 3], [2, 3, 1], [3, 1, 2] are all substrings of T.
std::vector<long long> text = b; // Start with `b`.
// Append the prefix `b[0...L-2]` only if L > 1. If L=1, the prefix is empty.
if (L > 1) {
// `b.begin() + L - 1` points one past the element at index L-2.
// `insert` appends elements from the range [first, last) to the end of `text`.
text.insert(text.end(), b.begin(), b.begin() + L - 1);
}
// If L=1, `text` remains just `b`. The KMP search `kmp_search(b, p)` will correctly compare the single elements.
// Use the KMP algorithm to search for `p` as a contiguous substring within `text`.
return kmp_search(text, p);
}
int main() {
// Use faster I/O streams for competitive programming.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Size of the array.
std::cin >> N;
std::vector<long long> A(N); // The input array.
std::vector<long long> S(N); // S will store the sorted version of A.
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
S[i] = A[i]; // Copy A to S initially.
}
// Sort S to get the target non-decreasing array.
std::sort(S.begin(), S.end());
// Find the largest index `k` (1-based) such that A[k-1] != S[k-1].
// This `k` represents the length of the shortest prefix of A that contains all elements
// that are not in their final sorted positions. If the array is already sorted, k will be 0.
int k = 0;
for (int i = N - 1; i >= 0; --i) {
if (A[i] != S[i]) {
k = i + 1; // Found the last mismatch; k is its 1-based index.
break; // Exit the loop once the largest index `k` is found.
}
}
// Case 1: The array is already sorted (k = 0).
if (k == 0) {
std::cout << 0 << std::endl; // No tools needed.
return 0;
}
// Case 2: Check if using only tool C_k is sufficient.
// This requires the prefix A[0...k-1] (length k) to be a cyclic shift of S[0...k-1].
// Create vector slices (copies) for these prefixes.
std::vector<long long> A_prefix_k(A.begin(), A.begin() + k);
std::vector<long long> S_prefix_k(S.begin(), S.begin() + k);
if (is_cyclic_shift(A_prefix_k, S_prefix_k)) {
// If it's a cyclic shift, one tool (C_k) is sufficient.
std::cout << 1 << std::endl;
return 0;
}
// Case 3: If tool C_k failed, check if tool C_{k+1} alone might be sufficient.
// This check is only relevant if such a tool exists (i.e., k < N).
if (k < N) {
// A necessary condition for tool C_{k+1} to potentially work is that the element
// at index k (the (k+1)-th element, A_{k+1} in 1-based indexing) must already be
// in its correct sorted position (A[k] == S[k]). This is because C_{k+1} affects
// the first k+1 elements, and all elements from index k+1 onwards must be correct
// if we only use tool C_{k+1}. By definition of k, elements A[k+1], A[k+2], ... A[N-1]
// are already equal to S[k+1], S[k+2], ... S[N-1]. So we only need to check A[k] == S[k].
if (A[k] == S[k]) {
// If the necessary condition holds, we then check the main condition:
// Is the prefix A[0...k] (length k+1) a cyclic shift of S[0...k]?
// Create vector slices for prefixes of length k+1.
std::vector<long long> A_prefix_k1(A.begin(), A.begin() + k + 1);
std::vector<long long> S_prefix_k1(S.begin(), S.begin() + k + 1);
if (is_cyclic_shift(A_prefix_k1, S_prefix_k1)) {
// If it is a cyclic shift, then one tool (C_{k+1}) is sufficient.
std::cout << 1 << std::endl;
return 0;
}
// If A[k] == S[k] but the cyclic shift check fails for length k+1,
// then C_{k+1} alone is not enough. Since C_k also failed, we need at least 2 tools.
// We know 2 tools are sufficient (e.g., C_k and C_{k+1}), so we fall through to output 2.
}
// else (A[k] != S[k]): The necessary condition A[k] == S[k] fails.
// Therefore, tool C_{k+1} cannot sort the array alone.
// Since C_k also failed, at least 2 tools are needed.
// We know 2 tools are sufficient (e.g., C_k and C_N), so we fall through to output 2.
}
// else (k == N): Tool C_k (which is C_N) failed. There is no tool C_{k+1}.
// At least 2 tools are needed.
// We know 2 tools are sufficient (e.g., C_{N-1} and C_N), so we fall through to output 2.
// Case 4: If we have reached this point, it means neither check for 1 tool succeeded.
// Our analysis showed that 2 tools are always sufficient if 1 tool is not.
std::cout << 2 << std::endl;
return 0;
}