codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1635C.md (2092B)


      1 Source: https://codeforces.com/problemset/problem/1635/C
      2 
      3 C. Differential Sorting
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $a$ of $n$ elements.
     22 
     23 Your can perform the following operation no more than $n$ times: Select three indices $x,y,z$ $(1 \leq x \lt y \lt z \leq n)$ and replace $a_x$ with $a_y - a_z$. After the operation, $|a_x|$ need to be less than $10^{18}$.
     24 
     25 Your goal is to make the resulting array non-decreasing. If there are multiple solutions, you can output any. If it is impossible to achieve, you should report it as well.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line will contain a single integer $t$ $(1 \leq t \leq 10000)$ — the number of test cases. Then $t$ test cases follow.
     30 
     31 The first line of each test case contains a single integer $n$ $(3 \leq n \leq 2 \cdot 10^5)$ — the size of the array $a$.
     32 
     33 The second line of each test case contains $n$ integers $a_1, a_2, \ldots ,a_n$ $(-10^9 \leq a_i \leq 10^9)$, the elements of $a$.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, print $-1$ in a single line if there is no solution. Otherwise in the first line you should print a single integer $m$ $(0 \leq m \leq n)$ — number of operations you performed.
     40 
     41 Then the $i$-th of the following $m$ lines should contain three integers $x,y,z$ $(1 \leq x \lt y \lt z \leq n)$— description of the $i$-th operation.
     42 
     43 If there are multiple solutions, you can output any. Note that you don't have to minimize the number of operations in this task.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 5
     52 5 -4 2 -1 2
     53 3
     54 4 3 2
     55 3
     56 -3 -2 -1
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 2
     63 1 2 3
     64 3 4 5
     65 -1
     66 0
     67 ```
     68 
     69 Note
     70 
     71 In the first example, the array becomes
     72 
     73 $[-6,-4,2,-1,2]$ after the first operation,
     74 
     75 $[-6,-4,-3,-1,2]$ after the second operation.
     76 
     77 In the second example, it is impossible to make the array sorted after any sequence of operations.
     78 
     79 In the third example, the array is already sorted, so we don't need to perform any operations.