oj.uz

Submission #404132

# Submission time Handle Problem Language Result Execution time Memory
404132 2021-05-13T20:25:09 Z penguinhacker Doktor (COCI17_doktor) C++14
100 / 100
 193 ms 36060 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=5e5;
int n, a[mxN], p[mxN], s[mxN];
vector<int> oc[mxN];
ar<int, 3> ans;

int pre(int i) {return i>=0?p[i]:0;}
int suf(int i) {return i<n?s[i]:0;}

void solve(int x) {
	for (int i=0; i<n; ++i) {
		int j=i+a[i];
		if (j%2==x)
			oc[j/2].push_back(abs(j/2-min(i, a[i])));
	}
	for (int i=0; i<n; ++i) {
		sort(oc[i].begin(), oc[i].end());
		int cur=0;
		for (int j : oc[i]) {
			++cur;
			int cur2=cur+pre(i-j-1)+suf(i+j+1+x);
			ans=max(ans, {cur2, i-j, i+j+x});
		}
		oc[i].clear();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i) {
		cin >> a[i], --a[i];
		p[i]=(i?p[i-1]:0)+(i==a[i]);
	}
	for (int i=n-1; ~i; --i)
		s[i]=(i+1<n?s[i+1]:0)+(i==a[i]);
	ans={s[0], 0, 0};
	solve(0), solve(1);
	cout << a[ans[1]]+1 << " " << a[ans[2]]+1;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11980 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 8 ms 12076 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12208 KB Output is correct
2 Correct 8 ms 12108 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12180 KB Output is correct
2 Correct 8 ms 12072 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12348 KB Output is correct
2 Correct 82 ms 19648 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15156 KB Output is correct
2 Correct 31 ms 14404 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 29776 KB Output is correct
2 Correct 129 ms 23376 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 22384 KB Output is correct
2 Correct 120 ms 36060 KB Output is correct