oj.uz

Submission #116830

# Submission time Handle Problem Language Result Execution time Memory
116830 2019-06-14T02:04:31 Z HungAnhGoldIBO2020 Doktor (COCI17_doktor) C++11
100 / 100
 383 ms 42744 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23936 KB Output is correct
2 Correct 21 ms 23808 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24192 KB Output is correct
2 Correct 153 ms 28012 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 26568 KB Output is correct
2 Correct 62 ms 25072 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 39020 KB Output is correct
2 Correct 243 ms 33220 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 32844 KB Output is correct
2 Correct 219 ms 42744 KB Output is correct