oj.uz

Submission #235435

# Submission time Handle Problem Language Result Execution time Memory
235435 2020-05-28T09:24:23 Z VEGAnn Doktor (COCI17_doktor) C++14
100 / 100
 243 ms 39776 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23936 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23936 KB Output is correct
2 Correct 20 ms 23936 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23924 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24320 KB Output is correct
2 Correct 64 ms 31260 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26744 KB Output is correct
2 Correct 36 ms 25852 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 39776 KB Output is correct
2 Correct 93 ms 34152 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 33272 KB Output is correct
2 Correct 75 ms 30840 KB Output is correct