Submission #559640

#	Time	Username	Problem	Language	Result	Execution time	Memory
559640		Trunkty	Doktor (COCI17_doktor)	C++14	100 / 100	244 ms	62340 KiB

doktor

#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 / 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