Submission #1310415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310415		ayuxhkumxr22	Doktor (COCI17_doktor)	C++20	100 / 100	107 ms	41952 KiB

doktor

/*
Author : ayuxh
*/
#include <bits/stdc++.h>
using namespace std;

// Speed up C++ I/O
void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 500005;
int p[MAXN];          // Permutation
int pref[MAXN];       // Prefix sum of original fixed points
vector<int> groups[2 * MAXN]; // Groups based on i + p[i]

void Solve() {
    int n;
    if (!(cin >> n)) return;

    // Read input and build prefix sums of original fixed points
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        pref[i] = pref[i - 1] + (p[i] == i ? 1 : 0);
        
        // Group indices by the required center sum (L+R)
        // For an element at i to be fixed after swap L..R,
        // it must end up at index p[i]. 
        // Swap maps i -> L+R-i. So we need p[i] = L+R-i => L+R = p[i]+i.
        groups[p[i] + i].push_back(i);
    }

    int max_fixed = -1;
    int best_L = 1, best_R = 1;
    
    // Initial baseline: 0 reversal (L=1, R=1 technically reverses single element)
    // The loop below will check all valid non-trivial reversals.
    // We should initialize with the 'no-op' count (which is pref[n]).
    // But we are maximizing the formula: (New inside) - (Old inside).
    // The base fixed count is added at the end or we track net change.
    // Let's track max TOTAL fixed points.
    
    // Initialize with Identity transform (L=1, R=1)
    max_fixed = pref[n]; 
    best_L = p[1]; 
    best_R = p[1];

    // Iterate over all possible center sums
    for (int s = 2; s <= 2 * n; ++s) {
        if (groups[s].empty()) continue;

        // Sort candidates by proximity to the center s/2
        // We want to expand outwards.
        // Distance of i from center is |i - s/2|.
        // Since we are iterating s, s is constant.
        // We can just sort by index and use two pointers or sort by distance.
        // Since elements in groups[s] are naturally somewhat ordered if we pushed in order,
        // let's just use the median-out expansion.
        
        // Actually, 'groups' is already sorted by index i because we pushed i=1..N.
        // The indices are i_1 < i_2 < ... < i_k.
        // The "center" is s/2.
        // We need to pair indices that are symmetric?
        // No, any range [L, R] with L+R=S will cover a subset of these candidates.
        // The optimal range for a fixed S must have boundaries L and R that are
        // "close" to the actual candidates to minimize empty space (which costs old fixed points).
        // Actually, simply iterating through the candidates in the group is enough.
        
        // For a fixed S, and a chosen candidate range inside the group (from index u to v in the vector),
        // The actual array indices are L = groups[s][u] and R = groups[s][v].
        // Wait, NO. If we pick range [L, R], we get points for ALL k such that L <= k <= R AND k is in groups[s].
        // But we must enforce L + R = S.
        // So L determines R. R = S - L.
        // So we can't pick arbitrary u and v.
        // We pick a "radius".
        // Let center be C = s/2.0.
        // For each i in groups[s], radius is |i - C|.
        // Sort candidates by radius.
        
        vector<int>& vec = groups[s];
        // Sort by distance to center |2*i - s|
        sort(vec.begin(), vec.end(), [&](int a, int b){
            return abs(2 * a - s) < abs(2 * b - s);
        });

        int current_new_points = 0;
        
        for (int i = 0; i < vec.size(); ++i) {
            int idx = vec[i];
            // Expand range to include this candidate
            // The range must be symmetric around S.
            // Boundaries are min(idx, s-idx) and max(idx, s-idx).
            int L = min(idx, s - idx);
            int R = max(idx, s - idx);
            
            // Increment new points count
            current_new_points++;
            
            // Calculate Old Points lost in this range
            int old_points_lost = pref[R] - pref[L - 1];
            
            int net_fixed = (pref[n] - old_points_lost) + current_new_points;
            
            if (net_fixed > max_fixed) {
                max_fixed = net_fixed;
                best_L = p[L];
                best_R = p[R];
            }
        }
    }

    cout << best_L << " " << best_R << "\n";
}

int main() {
    fast_io();
    Solve();
    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