oj.uz

Submission #235433

# Submission time Handle Problem Language Result Execution time Memory
235433 2020-05-28T09:22:13 Z VEGAnn Doktor (COCI17_doktor) C++14
0 / 100
 251 ms 43000 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]));

        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23936 KB Output isn't correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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