oj.uz

Submission #116924

# Submission time Handle Problem Language Result Execution time Memory
116924 2019-06-14T05:09:14 Z Dajunctic Doktor (COCI17_doktor) C++17
100 / 100
 377 ms 42744 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 21 ms 23808 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23908 KB Output is correct
2 Correct 21 ms 23808 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24184 KB Output is correct
2 Correct 151 ms 30060 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 26704 KB Output is correct
2 Correct 62 ms 25456 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 39432 KB Output is correct
2 Correct 246 ms 31808 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 32972 KB Output is correct
2 Correct 215 ms 42744 KB Output is correct