Submission #116924

#	Time	Username	Problem	Language	Result	Execution time	Memory
116924		Dajunctic	Doktor (COCI17_doktor)	C++17	100 / 100	377 ms	42744 KiB

doktor

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, a[N];
typedef pair<int,int> ii;
#define fi first
#define se second
int pre[N];
vector<ii> Split[N<<1];
int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		ii Sw = {i,a[i]};
		if(i>a[i]) swap(Sw.fi,Sw.se);
		Split[i+a[i]].push_back(Sw);
		pre[i] = pre[i-1] + (i==a[i]);
	}
	int ans = pre[n];
	ii bes = {1,1};
	for(int x=2;x<=(n<<1);x++){
		if(!Split[x].empty()){
			sort(Split[x].begin(),Split[x].end());
			reverse(Split[x].begin(),Split[x].end());
		}
		for(int i=0;i<Split[x].size();i++){
			ii katarina = Split[x][i];
			int num	= i + 1 + pre[n] - (pre[katarina.se] - pre[katarina.fi-1]);
			if (num > ans) {
				ans = num;
				bes = katarina;
			}
		}
	}
	cout << a[bes.fi] << " " << a[bes.se];
	return 0;
}

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<Split[x].size();i++){
               ~^~~~~~~~~~~~~~~~

• 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