Submission #97829

#TimeUsernameProblemLanguageResultExecution timeMemory
97829dalgerokDoktor (COCI17_doktor)C++17
100 / 100
317 ms45944 KiB
#include<bits/stdc++.h> using namespace std; const int N = 5e5 + 5; int n, a[N], pref[N]; vector < pair < int, int > > q[2 * N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; pref[i] = pref[i - 1] + (a[i] == i); int l = i, r = a[i]; if(l > r){ swap(l, r); } q[l + r].push_back(make_pair(l, r)); } pair < int, pair < int, int > > ans = make_pair(pref[n], make_pair(1, 1)); for(int i = 1; i <= 2 * n; i++){ if(q[i].empty()){ continue; } sort(q[i].rbegin(), q[i].rend()); for(int j = 0; j < (int)q[i].size(); j++){ int l = q[i][j].first, r = q[i][j].second; int val = j + 1 + pref[n] - (pref[r] - pref[l - 1]); ans = max(ans, make_pair(val, q[i][j])); } } cout << a[ans.second.first] << " " << a[ans.second.second]; }
#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...