Submission #82329

#	Time	Username	Problem	Language	Result	Execution time	Memory
82329		fredbr	Doktor (COCI17_doktor)	C++17	100 / 100	166 ms	17924 KiB

doktor

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000000;

int v[maxn];
int d[maxn];
int f[maxn*2];
int l[maxn*2];
int cnt[maxn*2];
int pref[maxn*2];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {

		int a;
		cin >> a;

		pref[i] = pref[i-1];
		if (a == i) pref[i]++;

		v[i] = a;

		d[i] = i-n+a-1;

		if (f[d[i]+n] == 0) f[d[i]+n] = i;
		l[d[i]+n] = i;
		cnt[d[i]+n]++;
	}

	for (int i = 0; i <= 2*n; i++) {

		if (f[i] == 0) continue;
		int ini = min(1+n-(l[i]-d[l[i]]), f[i]);
		int fim = max(1+n-(f[i]-d[l[i]]), l[i]);

		if (ini == fim) continue;

		cnt[i] -= pref[fim]-pref[ini-1];
	}

	int dbest = -1;
	int di;
	for (int i = 0; i <= 2*n; i++) {

		if (cnt[i] > dbest) {

			dbest = cnt[i];
			di = i;
		}
	}

	int ini = min(1+n-(l[di]-d[l[di]]), f[di]);
	int fim = max(1+n-(f[di]-d[l[di]]), l[di]);

	cout << v[ini] << " " << v[fim] << "\n";

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10