Submission #116916

#TimeUsernameProblemLanguageResultExecution timeMemory
116916nhimnam120Doktor (COCI17_doktor)C++14
100 / 100
288 ms46508 KiB
#include<bits/stdc++.h> using namespace std; long long fixedd[500005]; long long a[500005]; vector<long long> tam1[500005]; vector<long long> tam2[500005]; long long ans1,ans2; signed main(){ ios_base::sync_with_stdio(0); long long n; cin >> n; for(long long i=1;i<=n;i++){ cin >> a[i]; fixedd[i]=fixedd[i-1]; if(a[i]==i){ fixedd[i]++; } if((a[i]+i)%2==0){ tam1[(a[i]+i)/2].push_back(abs(a[i]-i)/2); } else{ tam2[(a[i]+i)/2].push_back(abs(a[i]-i)/2); } } ans1 = a[1]; ans2 = a[1]; long long mdx= -1000; for(long long i=1;i<=n;i++){ if(tam1[i].size()==0){ continue; } sort(tam1[i].begin(),tam1[i].end()); for(long long j = tam1[i].size() - 1; j >= 0; j--){ if(mdx < (j + 1 - fixedd[tam1[i][j] + i] + fixedd[i - tam1[i][j] - 1])){ mdx = j + 1 - fixedd[tam1[i][j] + i] + fixedd[i - tam1[i][j] - 1]; ans1 = a[i - tam1[i][j]]; ans2 = a[i + tam1[i][j]]; } } } for(long long i = 1; i < n; i++){ if(!tam2[i].size()) continue; sort(tam2[i].begin(), tam2[i].end()); for(long long j = tam2[i].size() - 1; j >= 0; j--){ if(mdx < (j + 1 - fixedd[tam2[i][j] + i + 1] + fixedd[i - tam2[i][j] - 1])){ mdx = j + 1 - fixedd[tam2[i][j] + i + 1] + fixedd[i - tam2[i][j] - 1]; ans1 = a[i - tam2[i][j]]; ans2 = a[i + tam2[i][j] + 1]; } } } cout << ans1 << " " << ans2; }
#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...