Submission #1309754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309754		ayuxhkumxr22	Doktor (COCI17_doktor)	C++20	100 / 100	116 ms	41864 KiB

doktor

/**
 * Problem: COCI 2017/2018 Round 2 - Doktor
 * Logic: Center Expansion / Contribution Technique
 * Complexity: O(N log N)
 */

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

using namespace std;

const int MAXN = 500005;

int N;
int A[MAXN];
int pref[MAXN]; // Prefix sum of original fixed points
vector<int> candidates[2 * MAXN]; // Group indices by sum (A[i] + i)

// Helper to get original fixed points in range [L, R]
int get_original_fixed(int L, int R) {
    if (L > R) return 0;
    return pref[R] - pref[L - 1];
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N)) return 0;

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    // 1. Precompute Original Fixed Points
    for (int i = 1; i <= N; i++) {
        pref[i] = pref[i - 1] + (A[i] == i ? 1 : 0);
    }

    // 2. Group candidates by invariant sum S = A[i] + i
    // Potential sums range from 1+1=2 to N+N=2N
    for (int i = 1; i <= N; i++) {
        int S = A[i] + i;
        candidates[S].push_back(i);
    }

    int best_gain = -1e9; // Initialize with a very low value
    int best_L = 1;
    int best_R = 1;

    // 3. Process each Sum group
    for (int S = 2; S <= 2 * N; S++) {
        if (candidates[S].empty()) continue;

        // We need to process nested intervals [L, R] where L + R = S.
        // The interval is defined by L. The closer L is to S/2, the smaller the interval.
        // We collect all L boundaries implied by the candidates.
        // For a candidate i, the minimal interval covering it is [min(i, S-i), max(i, S-i)].
        // Let's store the 'L' coordinate of these minimal intervals.
        
        vector<int> L_coords;
        for (int idx : candidates[S]) {
            int L = min(idx, S - idx);
            L_coords.push_back(L);
        }

        // Sort L_coords descending. 
        // Why? We start from the center (largest L) and expand outwards (smaller L).
        // Largest L corresponds to the smallest interval [L, S-L].
        sort(L_coords.begin(), L_coords.end(), greater<int>());

        int current_new_fixed = 0;
        
        // Iterate through unique L coordinates (distinct nested shells)
        for (size_t k = 0; k < L_coords.size(); ) {
            int curr_L = L_coords[k];
            int curr_R = S - curr_L;
            
            // Add all candidates that have this specific L boundary
            // (There might be multiple, e.g., i and S-i)
            int count_same_L = 0;
            while (k < L_coords.size() && L_coords[k] == curr_L) {
                count_same_L++;
                k++;
            }
            
            current_new_fixed += count_same_L;
            
            // Calculate Net Gain for interval [curr_L, curr_R]
            // Gain = (New Fixed Points) - (Original Fixed Points disrupted)
            int original_loss = get_original_fixed(curr_L, curr_R);
            int net_gain = current_new_fixed - original_loss;

            if (net_gain > best_gain) {
                best_gain = net_gain;
                best_L = curr_L;
                best_R = curr_R;
            }
        }
    }

    // Output the VALUES on the cards at the best range boundaries
    cout << A[best_L] << " " << A[best_R] << endl;

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10