oj.uz

Submission #82329

# Submission time Handle Problem Language Result Execution time Memory
82329 2018-10-30T02:02:19 Z fredbr Doktor (COCI17_doktor) C++17
100 / 100
 166 ms 17924 KB 
#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.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 500 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 43 ms 4120 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4120 KB Output is correct
2 Correct 22 ms 4120 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 17924 KB Output is correct
2 Correct 66 ms 17924 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 17924 KB Output is correct
2 Correct 82 ms 17924 KB Output is correct