Submission #1310417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310417		ayuxhkumxr22	Doktor (COCI17_doktor)	C++20	100 / 100	99 ms	42048 KiB

doktor

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

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 500005;
int p[MAXN];          
int pref[MAXN];       
vector<int> groups[2 * MAXN]; 

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

    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        pref[i] = pref[i - 1] + (p[i] == i ? 1 : 0);
        groups[p[i] + i].push_back(i);
    }

    // Initialize with the identity subarray (length 1)
    // To ensure lexicographically smallest, we pick the smallest value that is a fixed point?
    // Actually, identity means we reverse a range of length 1 (e.g., L=1, R=1).
    // The "values" are (p[1], p[1]).
    // To be strictly lexicographically smallest, we should initialize with the smallest p[i] 
    // such that we achieve the baseline score.
    // However, the loop covers all valid ranges. The baseline is effectively handled 
    // if we treat single elements as valid ranges.
    
    int max_fixed = pref[n]; 
    int best_val_L = p[1]; 
    int best_val_R = p[1];
    
    // Better initialization for lexicographical smallest:
    // Iterate 1..N to find the single element (i, i) that gives the smallest (p[i], p[i]).
    // Since we just want smallest p[i], and usually p is a permutation 1..N,
    // (1, 1) is the absolute smallest possible pair.
    // If we perform a "useless" swap (length 1), the score is always pref[n].
    // So we can safely initialize with (1, 1) if 1 exists in the array (which it does).
    best_val_L = 1; 
    best_val_R = 1;

    for (int s = 2; s <= 2 * n; ++s) {
        if (groups[s].empty()) continue;

        vector<int>& vec = groups[s];
        
        // Sort candidates by distance from center S/2 to expand outwards
        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];
            
            // Determine boundaries L and R for this candidate
            int L = min(idx, s - idx);
            int R = max(idx, s - idx);
            
            current_new_points++;
            
            int old_points_lost = pref[R] - pref[L - 1];
            int net_fixed = (pref[n] - old_points_lost) + current_new_points;
            
            int curr_val_L = p[L];
            int curr_val_R = p[R];

            // --- TIE BREAKER LOGIC ---
            bool better = false;
            if (net_fixed > max_fixed) {
                better = true;
            } else if (net_fixed == max_fixed) {
                // Lexicographical check: Minimize L value, then R value
                if (curr_val_L < best_val_L) {
                    better = true;
                } else if (curr_val_L == best_val_L && curr_val_R < best_val_R) {
                    better = true;
                }
            }

            if (better) {
                max_fixed = net_fixed;
                best_val_L = curr_val_L;
                best_val_R = curr_val_R;
            }
        }
    }

    cout << best_val_L << " " << best_val_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