LCC '18 Contest 5 S3 - Array Deletion

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Julian gave the following programming problem to his students : given an array of \(N\) elements, remove the \(M\) elements with indices \(K_1, K_2, ..., K_M\).

A common solution that his students submitted looked as follows:

for (int i = 0; i < m; ++i) { // Iterate over array K.
    A.remove(K.get(i)); // Remove K[i]th element from A.

Julian would like to show that this solution is incorrect. To do this, he would like to determine which elements are actually removed by this algorithm for a given input. Could you help him out?

Input Specification

The first line of input contains a two integers \(N, M\) \((1 \le N \le 10^9, 1 \le M \le 100,000)\), the number of elements in the array and the number of elements to remove. The next line of input contains \(M\) integers \(K_1, K_2, ..., K_M\) \((1 \le K_i \le N)\), the indices to remove.

For 30 of 100 points, \(1 \le N, M \le 1000\).
For 70 of 100 points, \(1 \le M \le 1000\).

Output Specification

If at some point, the incorrect program would attempt an index that is out-of-bounds, output Out of bounds. Otherwise, print the set of original indices removed by the incorrect solution in sorted order.

Sample Input 1

5 2
2 4

Sample Output 1

2 5

Sample Input 2

5 3
1 1 4

Sample Output 2

Out of bounds


There are no comments at the moment.