Submission #235435

#	Time	Username	Problem	Language	Result	Execution time	Memory
235435		VEGAnn	Doktor (COCI17_doktor)	C++14	100 / 100	243 ms	39776 KiB

doktor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MP make_pair
#define ft first
#define sd second
#define PB push_back
#define pli pair<ll,int>
#define pii pair<int,int>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
const int N = 1000100;
const int PW = 22;
const int oo = 2e9;
vector<array<int, 3> > mid[N];
int n, a[N], best = -oo, lf, rt, sum[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++){
        sum[i] = sum[i - 1];

        if (a[i] == i) {
            sum[i]++;
            continue;
        }

        int md = (a[i] + i);

        if (a[i] > i && a[a[i]] == i) continue;

        int nw = 1;

        if (a[a[i]] == i) nw++;

        mid[md].PB({min(i, a[i]), max(i, a[i]), nw});
    }

    for (int ps = 1; ps < N; ps++){
        if (sz(mid[ps]) == 0) continue;

        int med = -1;

        if (ps % 2 == 0)
            med = ps / 2;

        sort(all(mid[ps]));
        reverse(all(mid[ps]));

        int cnt = 0;

        for (array<int, 3> cr : mid[ps]){
            int len = (ps >> 1) - cr[0];

            if (med < 0)
                len++;

            cnt += cr[2];

            int cur = cnt - (sum[cr[1]] - sum[cr[0] - 1]);

            if (med >= 0)
                cur += (sum[med] - sum[med - 1]);

            if (cur > best){
                best = cur;
                lf = cr[0];
                rt = cr[1];
            }
        }
    }

    cerr << best << '\n';

    if (best < 0)
        cout << "1 1";
    else cout << a[lf] << " " << a[rt];

    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