PCPC12I - peaks

no tags 

 

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 Specification
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 Specification
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
Sample Output
3 4 5
1 4 5
 

 



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 Specification

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 Specification

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

Sample 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 ;-)
Note: It's Impossible to become faster than 0.15s because huge input data...

Last edit: 2013-01-05 21:19:20

Added by:abdelkarim
Date:2012-12-28
Time limit:0.371s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:The First Palestinian Collegiate Programming Contest