oj.uz

Submission #82243

# Submission time Handle Problem Language Result Execution time Memory
82243 2018-10-29T15:29:27 Z Leonardo_Paes Doktor (COCI17_doktor) C++11
60 / 100
 1000 ms 4476 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 5e5+100;
 
int num[maxn], soma[maxn], n;
 
int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin >> n;
 
	for (int i = 1; i <= n; i++)
	{
		cin >> num[i];
		if (num[i] == i) soma[i] = soma[i-1]+1;
		else soma[i] = soma[i-1];
	}
 
	int ans = 0, ind1 = num[1], ind2 = num[2];
 
	for (int i = 1; i <= n; i++)
	{
		if (num[i] < i) continue;
 
		int aux = soma[i-1]+soma[n]-soma[num[i]];
		for (int j = i; j <= num[i]; j++)
			if (num[j]+j == num[i]+i) aux++;
 
		if (aux > ans)
		{
			ans = aux;
			ind1 = num[i], ind2 = num[num[i]];
		}
	}
 
	for (int i = 1; i <= n; i++)
	{
		if (num[i] > i) continue;
 
		int aux = soma[n]-soma[i]+soma[num[i]-1];
		for (int j = num[i]; j <= i; j++)
			if (num[j]+j == num[i]+i) aux++;
 
		if (aux > ans)
		{
			ans = aux;
			ind1 = num[num[i]], ind2 = num[i];
		}
	}
 
	cout << ind1 << " " << ind2 << "\n";
}

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 448 KB Output is correct
2 Correct 2 ms 524 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 616 KB Output is correct
2 Correct 5 ms 616 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 732 KB Output is correct
2 Execution timed out 1063 ms 2944 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 2944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 4476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 4476 KB Time limit exceeded
2 Halted 0 ms 0 KB -