제출 #87817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87817		Koschei	Doktor (COCI17_doktor)	C++17	100 / 100	618 ms	55208 KiB

doktor

#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 / 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