結果

問題 No.958 たぷりすたべる (回文)
ユーザー qwewe
提出日時 2025-05-14 13:18:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,682 bytes
コンパイル時間 810 ms
コンパイル使用メモリ 78,688 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:19:10
合計ジャッジ時間 5,005 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

// Function to compute Manacher's algorithm results for odd length palindromes
// s: input string (1-based indexing is expected by the implementation)
// n: length of s
// returns: vector P where P[i] is the radius of the maximal odd palindrome centered at index i. 
// The length of the palindrome centered at i is 2*P[i] + 1.
std::vector<int> manacher_odd(const std::string& s, int n) {
    // P[i] stores the radius k. The palindrome is s[i-k..i+k].
    // Initialize radius vector P with size n+1 (for 1-based indexing) with all zeros.
    std::vector<int> P(n + 1, 0); 
    
    // l, r define the boundaries of the palindrome that extends furthest to the right.
    // Initially, the range [l, r] is empty, representing no palindrome found yet.
    // Using [1, 0] ensures the first center i=1 is not considered within r.
    int l = 1, r = 0; 
                      
    // Iterate through all possible centers i from 1 to n
    for (int i = 1; i <= n; ++i) {
        int k = 0; // Initialize radius k for center i
        
        // If center i is within the current rightmost palindrome [l, r]
        if (i <= r) {
            // Calculate the mirror index of i with respect to the center of the [l, r] palindrome.
            // The center is (l+r)/2. The mirror index is l + r - i.
            // We can leverage the already computed radius P[mirror].
            // The radius at i, k, is at least min(P[mirror], distance from i to the right boundary r).
             k = std::min(P[l + r - i], r - i);
        }
        
        // Attempt to expand the palindrome centered at i, starting from radius k.
        // Check characters symmetrically around i: s[i - (k+1)] and s[i + (k+1)].
        // Loop continues as long as indices are within bounds [1, n] and characters match.
        while (i - k - 1 >= 1 && i + k + 1 <= n && s[i - k - 1] == s[i + k + 1]) {
            k++; // Increase radius if characters match
        }
        
        P[i] = k; // Store the final computed radius for center i
        
        // If the palindrome centered at i [i-k, i+k] expands beyond the current rightmost boundary r,
        // update l and r to the boundaries of this new rightmost palindrome.
        if (i + k > r) {
            l = i - k; // New left boundary
            r = i + k; // New right boundary
        }
    }
    return P; // Return the computed radii vector
}


int main() {
    // Use fast I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long N_ll; // Use long long for N to potentially compute N*K without overflow
    long long K;    // K can be large
    int Q;          // Number of queries
    std::cin >> N_ll >> K >> Q;
    int N = static_cast<int>(N_ll); // N itself fits within int based on constraints (<= 2*10^5)

    std::string S_orig; // The base string S
    std::cin >> S_orig;

    // Handle the edge case N=0, though constraints state N >= 1.
    // If N were 0, T would be empty. Any query x would be invalid or trivial.
    // Given N >= 1, this check is technically not needed but safe.
    if (N == 0) {
         for (int i = 0; i < Q; ++i) {
              long long x;
              std::cin >> x; // Read the query position to consume input
              std::cout << 1 << "\n"; // An empty string conceptually might have a point center palindrome of length 1? Or 0? Sample behavior suggests 1.
         }
         return 0;
    }


    // Create S' = S + S. Manacher requires 1-based indexing.
    // Prepend a dummy character (space) to make the string 1-indexed.
    std::string S_doubled = S_orig + S_orig;
    std::string S_doubled_1based = " " + S_doubled; 
    
    int N_doubled = 2 * N; // Length of S'

    // Compute Manacher radii P' for S' using the implemented function
    std::vector<int> P_doubled = manacher_odd(S_doubled_1based, N_doubled);

    // Precompute the structural radii R[p] for each potential center p in S (p = 1..N)
    // R[p] represents the radius of the maximal palindrome centered at p in the infinite string T_infinity = SSS...
    std::vector<long long> R(N + 1); 
    for (int p = 1; p <= N; ++p) {
        long long r1 = P_doubled[p];         // Radius centered at p in S'
        long long r2 = P_doubled[p + N];     // Radius centered at p+N (corresponding position in the second S) in S'
        
        // Condition for infinite structural radius: 
        // Derived from the observation that if the palindromes centered at p and p+N in S'
        // "connect" or "overlap" sufficiently, the pattern repeats infinitely.
        // The condition r1 + r2 >= N - 1 captures this.
        if (r1 + r2 >= N - 1) {
            R[p] = -1; // Use -1 as a sentinel value to signify infinite radius
        } else {
            // If the structural radius is finite, it's determined by the palindrome centered at p within S'.
            // The radius cannot exceed what's computed by Manacher on S'.
            R[p] = r1; 
        }
    }

    // Process each query
    for (int i = 0; i < Q; ++i) {
        long long x; // Query position x can be large (up to KN)
        std::cin >> x;
        
        // Map the query position x in T to the corresponding position p in the base string S (1-based).
        // The modulo arithmetic finds the position within a block of S.
        int p = (x - 1) % N + 1;
        
        long long R_p = R[p]; // Fetch the precomputed structural radius for position p
        
        // Calculate the boundary limit R_max. This is the maximum possible radius centered at x
        // constrained by the boundaries of the full string T (length KN).
        // R_max = min(distance to left end T[1], distance to right end T[KN]).
        long long KN = K * N_ll; // Total length of T. Use N_ll (long long N) for calculation.
        long long R_max = std::min(x - 1, KN - x); // Both distances x-1 and KN-x must be non-negative.
        
        long long final_r; // The final maximal radius for the palindrome centered at x in T
        if (R_p == -1) { // Case 1: Structural radius is infinite
            final_r = R_max; // The radius is limited only by the boundaries of T.
        } else { // Case 2: Structural radius R_p is finite
             final_r = std::min(R_p, R_max); // The radius is limited by both the structure (R_p) and boundaries (R_max).
        }
        
        // The length of an odd palindrome with radius final_r is 2 * final_r + 1.
        long long length = 2 * final_r + 1;
        std::cout << length << "\n"; // Output the computed length
    }

    return 0; // Indicate successful execution
}
0