1983C.md (3891B)
1 Source: https://codeforces.com/problemset/problem/1983/C 2 3 C. Have Your Cake and Eat It Too 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 Alice, Bob and Charlie want to share a rectangular cake cut into $n$ pieces. Each person considers every piece to be worth a different value. The $i$-th piece is considered to be of value $a_i$ by Alice, $b_i$ by Bob and $c_i$ by Charlie. 22 23 The sum over all $a_i$, all $b_i$ and all $c_i$ individually is the same, equal to $tot$. 24 25 Given the values of each piece of the cake for each person, you need to give each person a contiguous slice of cake. In other words, the indices at the left and right ends of these subarrays (the slices given to each person) can be represented as $(l_a, r_a)$, $(l_b, r_b)$ and $(l_c, r_c)$ respectively for Alice, Bob and Charlie. The division needs to satisfy the following constraints: 26 27 * No piece is assigned to more than one person, i.e., no two subarrays among $[l_a,\ldots,r_a]$, $[l_b, \ldots, r_b]$ and $[l_c, \ldots, r_c]$ intersect. 28 * $ \sum_{i = l_a}^{r_a} a_i, \sum_{i = l_b}^{r_b} b_i, \sum_{i = l_c}^{r_c} c_i \geq \lceil \frac{tot}{3} \rceil$. 29 30 Here, the notation $\lceil \frac{a}{b} \rceil$ represents ceiling division. It is defined as the smallest integer greater than or equal to the exact division of $a$ by $b$. In other words, it rounds up the division result to the nearest integer. For instance $\lceil \frac{10}{3} \rceil = 4$ and $\lceil \frac{15}{3} \rceil = 5$. 31 32 Input 33 34 The first line contains an integer $t$, the number of testcases, ($1 \le t \le 10^4$) 35 36 For each testcase: 37 38 The first line contains the integer $n$ ($3 \le n \le 2 \cdot 10^5$). 39 40 The following three lines contain $n$ integers each: 41 42 One line with $n$ integers $a_1, a_2, \ldots, a_n$ represents the values for Alice ($1 \le a_i \le 10^6$). 43 44 The next line with $n$ integers $b_1, b_2, \ldots, b_n$ represents the values for Bob ($1 \le b_i \le 10^6$). 45 46 The next line with $n$ integers $c_1, c_2, \ldots, c_n$ represents the values for Charlie ($1 \le c_i \le 10^6$). 47 48 It is guaranteed that $ \sum_{i = 1}^{n} a_i = \sum_{i = 1}^{n} b_i = \sum_{i = 1}^{n} c_i$. 49 50 The sum of $n$ over all testcases does not exceed $2 \cdot 10^5$. 51 52 Output 53 54 For each testcase, output $-1$ if the required condition is impossible. 55 56 Otherwise, output six numbers – $l_a, r_a, l_b, r_b, l_c, r_c$, the respective starting and ending indices ($1$-indexed) of the subarrays for Alice, Bob and Charlie, respectively. 57 58 Example 59 60 Input 61 62 ``` 63 10 64 65 5 66 67 5 1 1 1 1 68 69 1 1 5 1 1 70 71 1 1 1 1 5 72 73 6 74 75 1 2 3 4 5 6 76 77 5 6 1 2 3 4 78 79 3 4 5 6 1 2 80 81 4 82 83 4 4 4 4 84 85 4 4 4 4 86 87 4 4 4 4 88 89 5 90 91 5 10 5 2 10 92 93 9 6 9 7 1 94 95 10 7 10 2 3 96 97 3 98 99 4 5 2 100 101 6 1 4 102 103 1 8 2 104 105 3 106 107 10 4 10 108 109 8 7 9 110 111 10 4 10 112 113 7 114 115 57113 65383 19795 53580 74452 3879 23255 116 117 12917 16782 89147 93107 27365 15044 43095 118 119 33518 63581 33565 34112 46774 44151 41756 120 121 6 122 123 6 3 1 8 7 1 124 125 10 2 6 2 2 4 126 127 10 9 2 1 2 2 128 129 5 130 131 5 5 4 5 5 132 133 1 6 3 8 6 134 135 2 4 1 9 8 136 137 10 138 139 1 1 1 1 1001 1 1 1001 1 1 140 141 1 1 1 1 1 1 2001 1 1 1 142 143 1 1 1 1 1 1001 1 1 1 1001 144 ``` 145 146 Output 147 148 ``` 149 1 1 2 3 4 5 150 5 6 1 2 3 4 151 -1 152 -1 153 1 1 3 3 2 2 154 -1 155 1 2 3 4 5 7 156 3 6 1 1 2 2 157 1 2 3 4 5 5 158 1 5 6 7 8 10 159 ``` 160 161 Note 162 163 In the first testcase, the sum of either of the three arrays is $9$. Each person needs a cake slice corresponding to a subarray with a total value of at least $\lceil \frac{9}{3} \rceil = 3$. 164 165 If we assign the subarray ($1$,$1$) to Alice, its total value to her is $5$, which is $\ge 3$; the subarray ($2$,$3$) to Bob, its total value to him is $1 + 5 = 6$, which is $\ge 3$; and the subarray ($4$,$5$) to Charlie, its total value to him $1 + 5 = 6$, which is also $\ge 3$. Each person gets their own separate pieces of the cake, and no piece is common to two or more people. 166 167 It can be shown that for the third test case, it is not possible to give slices of the cake in a way that satisfies the given constraints.