oj.uz

Submission #87817

# Submission time Handle Problem Language Result Execution time Memory
87817 2018-12-02T16:52:54 Z Koschei Doktor (COCI17_doktor) C++17
100 / 100
 618 ms 55208 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500666;

int n, m, h;
int a[MAXN], p[MAXN], ind[MAXN];
unordered_map<int, vector<int>> centres; 

bool kcmp(int a, int b)
{
	if (abs(a - ind[a]) < abs(b - ind[b])) return 1;
	else return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		 cin >> a[i];
		 p[i] = p[i-1] + (a[i] == i);
		 ind[a[i]] = i;	
	}
	for (int k = 1; k <= n; k++) centres[k + ind[k]].push_back(k);
	for (auto center : centres)
	{
		int d = 0;
		int c = center.first;
		sort(centres[c].begin(), centres[c].end(), kcmp);
		for (int k : centres[c])
		{
			int x = min(k, ind[k]);
			int y = max(k, ind[k]);
			int v = d + 1 + p[n] - p[y] + p[x-1];
			if (v > m)
			{
				m = v;
				h = k;
			}
			d++;
		}	
	}
	cout << a[min(h, ind[h])] << ' ' << a[max(h, ind[h])];
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1376 KB Output is correct
2 Correct 129 ms 6612 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7660 KB Output is correct
2 Correct 40 ms 7660 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 38416 KB Output is correct
2 Correct 228 ms 38416 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 38416 KB Output is correct
2 Correct 233 ms 55208 KB Output is correct