codeforces-scrape

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

1077C.md (2598B)


      1 Source: https://codeforces.com/problemset/problem/1077/C
      2 
      3 C. Good Array
      4 
      5 time limit per test
      6 
      7 1 second
      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 Let's call an array good if there is an element in the array that equals to the sum of all other elements. For example, the array $a=[1, 3, 3, 7]$ is good because there is the element $a_4=7$ which equals to the sum $1 + 3 + 3$.
     22 
     23 You are given an array $a$ consisting of $n$ integers. Your task is to print all indices $j$ of this array such that after removing the $j$-th element from the array it will be good (let's call such indices nice).
     24 
     25 For example, if $a=[8, 3, 5, 2]$, the nice indices are $1$ and $4$:
     26 
     27 * if you remove $a_1$, the array will look like $[3, 5, 2]$ and it is good;
     28 * if you remove $a_4$, the array will look like $[8, 3, 5]$ and it is good.
     29 
     30 You have to consider all removals independently, i. e. remove the element, check if the resulting array is good, and return the element into the array.
     31 
     32 Input
     33 
     34 The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$.
     35 
     36 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — elements of the array $a$.
     37 
     38 Output
     39 
     40 In the first line print one integer $k$ — the number of indices $j$ of the array $a$ such that after removing the $j$-th element from the array it will be good (i.e. print the number of the nice indices).
     41 
     42 In the second line print $k$ distinct integers $j_1, j_2, \dots, j_k$ in any order — nice indices of the array $a$.
     43 
     44 If there are no such indices in the array $a$, just print $0$ in the first line and leave the second line empty or do not print it at all.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 5
     52 2 5 1 2 2
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 3
     59 4 1 5
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 4
     66 8 3 5 2
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 2
     73 1 4
     74 ```
     75 
     76 Input
     77 
     78 ```
     79 5
     80 2 1 2 4 3
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 0
     87 ```
     88 
     89 Note
     90 
     91 In the first example you can remove any element with the value $2$ so the array will look like $[5, 1, 2, 2]$. The sum of this array is $10$ and there is an element equals to the sum of remaining elements ($5 = 1 + 2 + 2$).
     92 
     93 In the second example you can remove $8$ so the array will look like $[3, 5, 2]$. The sum of this array is $10$ and there is an element equals to the sum of remaining elements ($5 = 3 + 2$). You can also remove $2$ so the array will look like $[8, 3, 5]$. The sum of this array is $16$ and there is an element equals to the sum of remaining elements ($8 = 3 + 5$).
     94 
     95 In the third example you cannot make the given array good by removing exactly one element.