oj.uz

Submission #559640

# Submission time Handle Problem Language Result Execution time Memory
559640 2022-05-10T10:51:14 Z Trunkty Doktor (COCI17_doktor) C++14
100 / 100
 244 ms 62340 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

#define DEBUG
#ifdef DEBUG
  #define debug(x) cout << #x << ": " << x << endl
#else
  #define debug(x)
#endif

int n,ans,pa,pb;
int arr[500005],pre[500005],suf[500005];
vector<int> tot[1000005];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> arr[i];
		tot[arr[i]+i].push_back(i);
	}
	for(int i=1;i<=n;i++){
		pre[i] = pre[i-1];
		if(arr[i]==i){
			pre[i]++;
		}
	}
	for(int i=n;i>=1;i--){
		suf[i] = suf[i+1];
		if(arr[i]==i){
			suf[i]++;
		}
	}
	for(int i=1;i<=2*n;i++){
		int mid = (i+1)/2;
		vector<vector<int>> v; 
		int cnt=0;
		for(int j:tot[i]){
			v.push_back({abs(j-mid),j});
		}
		sort(v.begin(),v.end());
		for(vector<int> j:v){
			cnt++;
			int op = i-j[1];
			if(op<j[1]){
				if(ans<pre[op-1]+suf[j[1]+1]+cnt){
					ans = pre[op-1]+suf[j[1]+1]+cnt;
					pa = arr[op];
					pb = arr[j[1]];
				}
			}
			else{
				if(ans<pre[j[1]-1]+suf[op+1]+cnt){
					ans = pre[j[1]-1]+suf[op+1]+cnt;
					pa = arr[j[1]];
					pb = arr[op];
				}
			}
		}
	}
	cout << pa << " " << pb << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23812 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 13 ms 23884 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23956 KB Output is correct
2 Correct 15 ms 23816 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24204 KB Output is correct
2 Correct 16 ms 23836 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24148 KB Output is correct
2 Correct 131 ms 50932 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 27456 KB Output is correct
2 Correct 46 ms 31432 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 44120 KB Output is correct
2 Correct 225 ms 62340 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 35552 KB Output is correct
2 Correct 115 ms 47796 KB Output is correct