oj.uz

Submission #132829

# Submission time Handle Problem Language Result Execution time Memory
132829 2019-07-19T17:25:46 Z Ort Doktor (COCI17_doktor) C++11
100 / 100
 289 ms 45788 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#define MAX 500005

using namespace std;

int n, x, soll, solr, sol;
int arr[MAX], indx[MAX], lef[MAX], righ[MAX];
vector<vector<int> > a;

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	cin >> n; a.resize(n*2+1);
	for(int i=1;i<=n;i++) {
		cin >> arr[i];
		indx[arr[i]] = i;
		a[i+arr[i]].push_back(i);
	}
	for(int i=0;i<a.size();i++) sort(a[i].begin(),a[i].end());
	for(int i=1;i<=n;i++) righ[i] = righ[i-1]+(arr[i]==i);
	for(int i=n;i>0;i--) lef[i] = lef[i+1]+(arr[i]==i);
	for(int i=1;i<=n;i++) {
		int l=i, r=indx[i]; if(r<l) swap(r,l);
		int f = (upper_bound(a[l+r].begin(),a[l+r].end(),r) - lower_bound(a[l+r].begin(),a[l+r].end(),l));
		if(righ[l-1]+lef[r+1]+f > sol) {soll = l; solr = r; sol = righ[l-1]+lef[r+1]+f;}
	}
	cout << arr[soll] << " " << arr[solr];
	return 0;
}

Compilation message

doktor.cpp: In function 'int main()':
doktor.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++) sort(a[i].begin(),a[i].end());
              ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 632 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 107 ms 20432 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8056 KB Output is correct
2 Correct 35 ms 7108 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 42392 KB Output is correct
2 Correct 175 ms 33728 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 25052 KB Output is correct
2 Correct 131 ms 45788 KB Output is correct