oj.uz

Submission #87816

# Submission time Handle Problem Language Result Execution time Memory
87816 2018-12-02T16:51:47 Z Koschei Doktor (COCI17_doktor) C++17
90 / 100
 1000 ms 70744 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500666;

int n, m, h;
int a[MAXN], p[MAXN], ind[MAXN];
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 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1696 KB Output is correct
2 Correct 125 ms 8676 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 11520 KB Output is correct
2 Correct 41 ms 11520 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 52284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 52284 KB Output is correct
2 Correct 600 ms 70744 KB Output is correct