Submission #521451

#TimeUsernameProblemLanguageResultExecution timeMemory
521451Rasoul006Doktor (COCI17_doktor)C++17
10 / 100
1092 ms3688 KiB
#include <bits/stdc++.h> #define endl "\n" typedef long long ll; using namespace std; const int N = 1e6+5; ll n , a[200009] , pre[200009] ; 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]++ ; } } for(int i = 1 ;i <= n ;i++){ pre[i] += pre[i-1] ; } ll mx = 0 ; pair < ll , ll > best= {0 , 0} ; for(ll i = 1 ; i <= n ; i++){ ll l = min(i , a[i]) , r = max(i , a[i]) ; ll q = pre[a[i] - 1] + (pre[n] - pre[r]) ; // 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) ; } if(q >= mx){ mx = q ; best = {max(a[i] , i) , min(i , a[i])} ; } } cout << best.first << " " << best.second ; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...