oj.uz

Submission #473429

# Submission time Handle Problem Language Result Execution time Memory
473429 2021-09-15T13:49:33 Z _L__ Doktor (COCI17_doktor) C++14
70 / 100
 437 ms 41336 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 204 KB Output is correct
2 Correct 62 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 36 ms 6988 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 6388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 437 ms 33752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 19908 KB Output is correct
2 Correct 193 ms 41336 KB Output is correct