Submission #116902

#	Time	Username	Problem	Language	Result	Execution time	Memory
116902		tuanasanh	Doktor (COCI17_doktor)	C++14	100 / 100	279 ms	46592 KiB

doktor

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int,int> ii;
ii p;
int n,a[1000005],v[1000005],tmp,pref[1000005],suf[1000005];
vector<int> val[1000005];
int main(){
	ios::sync_with_stdio(false); cin.tie();cout.tie();
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>v[i];
		a[v[i]]=i;
		pref[i]=pref[i-1]+(v[i]==i);
	}
	for(int i=n;i>=1;i--) suf[i]=suf[i+1]+(v[i]==i);
	for(int i=1;i<=n;i++) val[i+a[i]].push_back(i);
	for(int i=1;i<1000005;i++) sort(val[i].begin(),val[i].end());
	for(int i=1;i<=n;i++){
		int l=min(i,a[i]),r=max(i,a[i]);
		int ans=upper_bound(val[i+a[i]].begin(),val[i+a[i]].end(),r)-lower_bound(val[i+a[i]].begin(),val[i+a[i]].end(),l)+suf[r+1]+pref[l-1]; 
		if(ans>tmp){
			tmp=ans;
			p={l,r};
		}
	}
	cout<<v[p.f]<<" "<<v[p.s];
}

• 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