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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define st first
#define nd second
const int N = 5e5+5;
int n, a[N];
int center[N];
int pref[N];
vector<pair<int,int>> seg[2*N];
int mx = -N;
pair<int,int> ans;
int cnt = 0;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] == i)
{
cnt++;
}
pref[i] = cnt;
center[i] = a[i]+i;
if (a[i] < i)
seg[center[i]].push_back({a[i],i});
else
seg[center[i]].push_back({i,a[i]});
}
for (int i = 1; i <= 3*n; i++)
{
if (seg[i].size() == 0) continue;
int tmp = 1 - (pref[seg[i][0].nd] - pref[seg[i][0].st-1]);
if (tmp > mx)
{
mx = tmp;
ans = seg[i][0];
}
sort(seg[i].begin(),seg[i].end(), greater<pair<int,int> >() );
for (int j = 1; j < seg[i].size(); j++)
{
int l = seg[i][j-1].st, r = seg[i][j-1].nd, L = seg[i][j].st, R = seg[i][j].nd;
tmp++;
tmp -= (pref[l-1] - pref[L-1] + pref[R] - pref[r]);
if (tmp > mx)
{
mx = tmp;
ans = seg[i][j];
}
}
}
cout << a[ans.st] << ' ' << a[ans.nd];
}
Compilation message (stderr)
doktor.cpp: In function 'int main()':
doktor.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < seg[i].size(); j++)
~~^~~~~~~~~~~~~~~
# | 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... |