oj.uz

Submission #80017

# Submission time Handle Problem Language Result Execution time Memory
80017 2018-10-18T08:37:48 Z pzdba Doktor (COCI17_doktor) C++14
80 / 100
 653 ms 25168 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;
	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

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 2 ms 508 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 508 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 508 KB Output is correct
2 Correct 3 ms 508 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 948 KB Output is correct
2 Correct 40 ms 1640 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 4152 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 653 ms 19416 KB Output is correct
2 Correct 92 ms 19416 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 19416 KB Output is correct
2 Correct 373 ms 25168 KB Output is correct