Submission #116830

#	Time	Username	Problem	Language	Result	Execution time	Memory
116830		HungAnhGoldIBO2020	Doktor (COCI17_doktor)	C++11	100 / 100	383 ms	42744 KiB

doktor

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
const int N=5e5+2;
vector<int> pos[N][2];
int ar[N],sum[N];
int main(){
	int n,i,j,k,pos1=0,max1=-1;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>ar[i];
		sum[i]=sum[i-1];
		if(ar[i]==i){
			pos1=i;
			sum[i]++;
		}
		if((ar[i]+i)%2==0){
			pos[(ar[i]+i)/2][0].push_back(i);
		}
		else{
			pos[(ar[i]+i)/2][1].push_back(i);
		}
	}
	for(i=1;i<=n;i++){
		j=ar[i];
		k=i;
		if(j>k){
			swap(j,k);
		}
		if((j+k)%2==0){
if(max1<(int)(upper_bound(pos[(j+k)/2][0].begin(),pos[(j+k)/2][0].end(),k)-lower_bound(pos[(j+k)/2][0].begin(),pos[(j+k)/2][0].end(),j))-(sum[k]-sum[j-1])){
	max1=(int)(upper_bound(pos[(j+k)/2][0].begin(),pos[(j+k)/2][0].end(),k)-lower_bound(pos[(j+k)/2][0].begin(),pos[(j+k)/2][0].end(),j))-(sum[k]-sum[j-1]);
	pos1=i;
}
		}
		else{
if(max1<(int)(upper_bound(pos[(j+k)/2][1].begin(),pos[(j+k)/2][1].end(),k)-lower_bound(pos[(j+k)/2][1].begin(),pos[(j+k)/2][1].end(),j))-(sum[k]-sum[j-1])){
	max1=(int)(upper_bound(pos[(j+k)/2][1].begin(),pos[(j+k)/2][1].end(),k)-lower_bound(pos[(j+k)/2][1].begin(),pos[(j+k)/2][1].end(),j))-(sum[k]-sum[j-1]);
	pos1=i;
}			
		}
	}
	//cout<<pos1<<endl;
	if(ar[pos1]<pos1){
		cout<<ar[ar[pos1]]<<" "<<ar[pos1];
	}
	else{
		cout<<ar[pos1]<<" "<<ar[ar[pos1]];
	}
}

• 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