Submission #96854

#	Time	Username	Problem	Language	Result	Execution time	Memory
96854		Rouge_Hugo	Doktor (COCI17_doktor)	C++14	90 / 100	1069 ms	59028 KiB

doktor

	#include <bits/stdc++.h>
	using namespace std;
	const int mw=5*100002;
	int pr[mw],a[mw],t[mw];
	map<double,vector<pair<int,int>>>m;
	int main()
	{ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
		int sum=0;
		int n;cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			t[a[i]]=i;
			if (a[i]==i)
			{
				sum++;	
			}
			pr[i]=sum;
		}
		for(int i=1;i<=n;i++)
		{
			double u=(a[i]+i)/2.0;
			m[u].push_back({min(a[i],i),max(a[i],i)});
		}
		int mx=0;
		pair<int,int>b;
		for(auto it :m)
		{sum=0;
		sort(m[it.first].begin(),m[it.first].end());
		reverse (m[it.first].begin(),m[it.first].end());
			for(auto pp:m[it.first])
			{
				if (mx<sum+1+pr[n]-pr[pp.second]+pr[pp.first-1])
				{
				mx=sum+1+pr[n]-pr[pp.second]+pr[pp.first-1];
				b=pp;
				}
			sum++;
			}
		}
		cout<<a[b.first]<<" "<<a[b.second];
			
	 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: 0 / 10
• Subtask 10: 10 / 10