PCPC12I - peaks
You are given a sequence of numbers s, you are required to find 3 indices i, j, k, where i < j < k and (s[i] <= s[j] >= s[k] or s[i] >= s[j] <= s[k]) if there are many solutions you should find the one where |s[i]-s[j]| + |s[j]-s[k]| is maximized, if there are still many solutions you should find the one which comes earlier in order (i.e. i1, j1, k1, comes before i2, j2, k2, if i1 < i2, or if i1 = i2, and j1 < j2, or if i1 = i2, j1 = j2, and k1 < k2).
Input
The problem will be tested on multiple test cases, the first line of the input contains an integer n representing the size of the sequence (3 <= n <= 10^6) (^ means power), then followed by n integers. All numbers in this sequence do not exceed 10^6 in absolute value. The input is terminated by end of file.
Output
For each test case, output a line containing the 3 indices of the pattern i, j, k space separated. If there is no such pattern output -1 instead.
Sample
Input: 7 2 3 1 7 2 4 8 5 2 3 5 7 1 Output: 3 4 5 1 4 5
hide comments
.:frUstrAteD:.:
2015-06-10 23:22:11
why pair of integer array works faster than two separate integer arrays -_- ?? |
|
(Tjandra Satria Gunawan)(曾毅昆):
2013-01-05 20:40:22
0.25s is my best speed ;-)
|
Added by: | abdelkarim |
Date: | 2012-12-28 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | The First Palestinian Collegiate Programming Contest |