# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
80017 | pzdba | Doktor (COCI17_doktor) | C++14 | 653 ms | 25168 KiB |
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>
using namespace std;
int a[500005];
map<int, int> dp;
map<int, int>::iterator its;
int main(){
int n;
scanf("%d", &n);
int ans = 0;
for(int i=1;i<=n;i++){
scanf("%d", &a[i]);
int diff = a[i]-i;
if(diff == 0) ans++;
diff += 2*i;
dp[diff]++;
}
int res = 0;
int idx = 0;
for(its = dp.begin();its != dp.end();its++){
int i = its->first;
if(dp[i] > res){
res = dp[i];
idx = i;
}
}
if(res == 0 || res <= ans){
printf("1 1\n");
return 0;
}
int st = 1e9, en = 0;
for(int i=1;i<=n;i++){
int diff = a[i]-i;
diff += 2*i;
if(diff == idx){
diff -= 2*i;
if(diff < 0){
st = min(st, i+diff);
en = max(en, i);
}
else{
st = min(st, i);
en = max(en, i+diff);
}
}
}
printf("%d %d\n", a[st], a[en]);
}
Compilation message (stderr)
# | 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... |