Submission #1340904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340904		orgiloogii	Doktor (COCI17_doktor)	C++20	100 / 100	122 ms	53312 KiB

doktor

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n;
    cin >> n;
    int a[n + 1];;
    int pref[n + 1] = {0};
    int suff[n + 2] = {0};
    vector <vector <int>> adj(2 * n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        adj[a[i] + i].push_back(i);
    }
    for (int i = 1;i <= n;i++) {
        pref[i] = pref[i - 1];
        if (a[i] == i) pref[i]++;
    }
    for (int i = n;i >= 1;i--) {
        suff[i] = suff[i + 1];
        if (a[i] == i) suff[i]++;
    }
    int ans = 0, l = 1, r = 1;
    for (int i = 1;i <= n;i++) {
        int x, y;
        if (i > a[i]) {
            x = a[i];
            y = i;
        }
        else {
            x = i;
            y = a[i];
        }
        auto it = lower_bound(adj[a[i] + i].begin(), adj[a[i] + i].end(), x);
        auto it1 = lower_bound(adj[a[i] + i].begin(), adj[a[i] + i].end(), y + 1); 
        int res = pref[x - 1] + (it1 - it) + suff[y + 1];
        if (res > ans) {
            ans = res;
            l = a[x];
            r = a[y];
        }
    }
    int ids[n + 1] = {0};
    for (int i = 1;i <= n;i++) {
        ids[a[i]] = i;
    }
    if (ids[l] > ids[r]) swap(l, r);
    cout << l << ' ' << r << endl;
}

• 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