oj.uz

Submission #80018

# Submission time Handle Problem Language Result Execution time Memory
80018 2018-10-18T08:39:07 Z pzdba Doktor (COCI17_doktor) C++14
80 / 100
 543 ms 25260 KB 
#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, 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("%d %d\n", a[1], a[1]);
		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

doktor.cpp: In function 'int main()':
doktor.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
doktor.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 440 KB Output is correct
2 Correct 3 ms 440 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 568 KB Output is correct
2 Correct 3 ms 568 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2 ms 568 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 42 ms 1736 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 19304 KB Output is correct
2 Correct 70 ms 19304 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 19304 KB Output is correct
2 Correct 335 ms 25260 KB Output is correct