Submission #82207

#	Time	Username	Problem	Language	Result	Execution time	Memory
82207		pamaj	Doktor (COCI17_doktor)	C++14	50 / 100	1080 ms	8620 KiB

doktor

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;

int v[maxn], pfsum[maxn] , n;
int pos[maxn];

int main()
{

	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> v[i];
		pos[v[i]] = i;
		if(v[i] == i) 
		{
			pfsum[i] = pfsum[i - 1] + 1;
		}
	}

	vector<pair<int, int>> p;

	for(int i = 1; i <= n; i++)
	{
		if(v[i] == i) continue;
		int ini = v[i], fim = pos[v[i]];
		if(ini > fim) swap(ini, fim);
		p.push_back({ini, fim});
	}

	int best = 0;
	pair<int, int> bp;
	for(auto u : p)
	{

		int ans = 0;
		int i = u.first, j = u.second;
		ans += pfsum[i - 1];
		ans += pfsum[n] - pfsum[j];

		int mid = (u.second - u.first)/2;
		for(int cont = 0; cont < mid; cont++)
		{
			swap(v[u.first + cont], v[u.second - cont]);
		} 
		for(int z = u.first; z <= u.second; z++)
		{
			if(v[z] == z) ans++;
		}
		for(int cont = 0; cont < mid; cont++)
		{
			swap(v[u.first + cont], v[u.second - cont]);
		}
		if(ans > best)
		{
			best = ans;
			bp.first = v[u.first], bp.second = v[u.second];
		}
	}

	//cout << best << "\n";
	if(bp.first == 0 and bp.second == 0) 
	{
		for(int i = 1; i <= n; i++)
		{
			if(v[i] == i) cout << i << " " << i << "\n";
			return 0;		
		}
	}

	cout << bp.first << " " << bp.second << "\n";

	return 0;
}

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