Submission #521463

#TimeUsernameProblemLanguageResultExecution timeMemory
521463Rasoul006Doktor (COCI17_doktor)C++17
10 / 100
1092 ms11736 KiB
#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++){ for(int j = i ; j <= n ; j++){ ll l = i , r = j ; 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 = {j , 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...