Submission #473429

#	Time	Username	Problem	Language	Result	Execution time	Memory
473429		_L__	Doktor (COCI17_doktor)	C++14	70 / 100	437 ms	41336 KiB

doktor

// This code is written by _L__
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define F_word ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
typedef long long ll;
typedef long double ld;
const ll mod = 1e9+7, N = 5e5+13, inf = 1e9+1;
const ld E = 1e-6;
#define ff first
#define ss second

ll n, a[N], pref[N];

void brute_force(){
    ll sum = 0, a_1 = 1, a_2 = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            reverse(a+i, a+j+1); ll x = 0;
            for(int k = 1; k <= n; ++k) x += (a[k] == k);
            if(x >= sum){a_1 = i, a_2 = j, sum = x;}
            reverse(a+i, a+j+1);
        }
    }
    cout << a[a_1] << ' ' << a[a_2] << endl;
} 

pair<pair<ll, ll>, ll> snek(ll a_odd){
    ll a_1 = a_odd, a_2 = a_odd, i = a_odd-1, j = a_odd+1, total = (a[a_1] == a_1), sum = 0;
    while(i > 0 && j <= n){
        ll c = (a[i]+i)/2; if(c==a_odd)++total;
        c=(a[j]+j)/2; if(c==a_odd)++total;
        ll x = total+pref[i-1]+(pref[n]-pref[j]);
        if(x>=sum){a_1 = i, a_2 = j, x = sum;}
        ++j; --i;
    }
    if(sum == 0) sum = pref[n];
    return {{a_1, a_2}, sum};
}

pair<pair<ll, ll>, ll> orochimaru(ll a_even){
    ll a_1 = a_even, a_2 = a_even+1, i = a_even-1, j = a_even+2, total = (a[a_1] == a_1)+(a[a_2] == a_1), sum = 0;
    while(i > 0 && j <= n){
        ll c = (a[i]+i)/2; if(c==a_even)++total;
        c=(a[j]+j)/2; if(c==a_even)++total;
        ll x = total+pref[i-1]+(pref[n]-pref[j]);
        if(x>=sum){a_1 = i, a_2 = j, x = sum;}
        ++j; --i;
    }
    if(sum == 0) sum = pref[n];
    return {{a_1, a_2}, sum};
}

int main(void){
    F_word;
    cin >> n; for(int i = 1; i <= n; ++i){cin>>a[i];pref[i] += pref[i-1]; pref[i]+=(a[i]==i);}
    if(n <= 500){brute_force(); return 0;}
    map<ll, ll>even, odd;
    for(int i = 1; i <= n; ++i){
        if(!((a[i]-i)%2)) ++odd[(a[i]+i)/2];
        else ++even[(a[i]+i)/2];
    }
    ll a_even = 0, a_odd = 0, tar = 0;
    for(auto u: even)
        if(tar <= u.ss){tar = u.ss; a_even = u.ff;}
    tar = 0;
    for(auto u: odd)
        if(tar <= u.ss){tar = u.ss; a_odd = u.ff;}
    if(a_odd == 0 && a_even == 0)return cout << "1 1\n", 0;
    if(a_even == 0){
        pair<pair<ll, ll>, ll> x = snek(a_odd);
        cout << a[x.ff.ff] << ' ' << a[x.ff.ss] << endl;
    } else if(a_odd == 0) {
        pair<pair<ll, ll>, ll> x = orochimaru(a_even);
        cout << a[x.ff.ff] << ' ' << a[x.ff.ss] << endl;
    } else {
        pair<pair<ll, ll>, ll> pain = snek(a_odd), konan = orochimaru(a_even);
        if(pain.ss >= konan.ss) cout << a[pain.ff.ff] << ' ' << a[pain.ff.ss] << endl;
        else cout << a[konan.ff.ff] << ' ' << a[konan.ff.ss] << endl;
    }
} 

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