Submission #80018

#	Time	Username	Problem	Language	Result	Execution time	Memory
80018		pzdba	Doktor (COCI17_doktor)	C++14	80 / 100	543 ms	25260 KiB

doktor

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10