Submission #237919

#	Time	Username	Problem	Language	Result	Execution time	Memory
237919		MrRobot_28	Doktor (COCI17_doktor)	C++17	100 / 100	733 ms	52568 KiB

doktor

#include<bits/stdc++.h>
using namespace std;

bool cmp(pair <pair <int, int>, pair <int, int> > a, pair <pair <int, int>, pair <int, int> > b)
{
	return a.second.second - a.first.second < b.second.second - b.first.second; 
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	vector <int> a(n);
	set <pair <pair <int, int>, pair <int, int> > > st;
	vector <int> cnt1(n), cnt2(n);
	vector <pair <pair <int, int>, pair <int, int> > > vec;
	vector <int> pref(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		a[i]--;
		if(i == a[i])
		{
			pref[i]++;
		}
		if(i != 0)
		{
			pref[i] += pref[i - 1];
		}
		int len = fabs(a[i] - i) + 1;
		int l = i, r = a[i];
		if(l > r)
		{
			swap(l, r);
		}
		if(len % 2 == 0)
		{
			vec.push_back({{l + len / 2 - 1, 0}, {l, r}});
		}
		else
		{
			vec.push_back({{l + len / 2, 1}, {l, r}});
		}
	}
	sort(vec.begin(), vec.end(), cmp);
	vector <int> add(vec.size());
	for(int i = 0; i < vec.size(); i++)
	{
		set <pair <pair <int, int>, pair <int, int> > > :: iterator it;
		it = st.lower_bound({vec[i].first, {vec[i].second.first, 0}});
		if(it != st.end() && it -> first == vec[i].first)
		{
			add[i] += add[it -> second.second];
		}
		add[i]++;
		st.insert({vec[i].first, {vec[i].second.first, i}});
	}
	int ans = 0, ansl = a[0], ansr = a[0];
	for(int i = 0; i < vec.size(); i++)
	{
		int l = vec[i].second.first;
		int r = vec[i].second.second;
		int val = add[i];
		if(l != 0)
		{
			val += pref[l - 1];
		}
		val -= pref[r];
		if((r - l + 1) % 2 == 1 && a[(r + l) / 2] == (r + l) / 2)
		{
			val++;
		}
		if(val > ans)
		{
			ans = val;
			ansl = a[l];
			ansr = a[r];
		}
	}
	cout << ansl + 1 << " " << ansr + 1;
	return 0;
}

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vec.size(); i++)
                 ~~^~~~~~~~~~~~
doktor.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vec.size(); i++)
                 ~~^~~~~~~~~~~~

• 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