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>
#define endl "\n"
typedef long long ll;
using namespace std;
const int N = 1e6+5;
ll n , a[500009] , suf[500009] , pre[500009] ;
map < ll , ll > mp ;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n ;
for(int i = 1 ; i <= n ; i++){
cin >> a[i] ;
if(a[i] == i){
pre[i]++ ;
suf[i]++ ;
}
}
for(int i = 1 ;i <= n ;i++){
pre[i] += pre[i-1] ;
}
for(int i = n ;i >= 1 ; i--){
suf[i] += suf[i + 1] ;
}
ll mx = pre[n] ;
pair < ll , ll > best = {1 , 1} ;
for(ll i = 1 ; i <= n ; i++){
ll l = min(a[i] , i) , r = max(i , a[i]) ;
ll q = (pre[l - 1] + suf[r + 1]) ;
// cout << i << " " << j << " " << q << endl ;
// cout << suf[r + 1] << " " << pre[l - 1] << endl ;
// cout << l << " " << r << " " ;
// cout << pre[a[i] - 1] << " " << pre[n] - pre[r]<< endl ;
while(r > l){
q += ((a[r] == l) + (a[l] == r)) ;
l++ , r-- ;
}
if(l == r){
q += (a[r] == r) ;
}
// cout << q << endl ;
if(q >= mx){
mx = q ;
best = {min(a[i] , i) , max(a[i] , i)} ;
}
}
cout << a[best.first] << " " << a[best.second] ;
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... |