This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=5e5;
int n, a[mxN], p[mxN], s[mxN];
vector<int> oc[mxN];
ar<int, 3> ans;
int pre(int i) {return i>=0?p[i]:0;}
int suf(int i) {return i<n?s[i]:0;}
void solve(int x) {
for (int i=0; i<n; ++i) {
int j=i+a[i];
if (j%2==x)
oc[j/2].push_back(abs(j/2-min(i, a[i])));
}
for (int i=0; i<n; ++i) {
sort(oc[i].begin(), oc[i].end());
int cur=0;
for (int j : oc[i]) {
++cur;
int cur2=cur+pre(i-j-1)+suf(i+j+1+x);
ans=max(ans, {cur2, i-j, i+j+x});
}
oc[i].clear();
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i=0; i<n; ++i) {
cin >> a[i], --a[i];
p[i]=(i?p[i-1]:0)+(i==a[i]);
}
for (int i=n-1; ~i; --i)
s[i]=(i+1<n?s[i+1]:0)+(i==a[i]);
ans={s[0], 0, 0};
solve(0), solve(1);
cout << a[ans[1]]+1 << " " << a[ans[2]]+1;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |