z-01seq
You are given a sequence of length N containing only 0s and 1s. You should find exactly 2 * K different indices ai among which there must be exactly K indices of 1s and exactly K indices 0s in the given sequence (the indices are 0-based, and you should output them in increasing order - such that for each j < k, aj < ak) .
In the case of multiple solutions return the set of indices such that Sum of (aj + 1 - aj), 0 < j < 2K, is minimal. If there are still multiple solution, return the lexicographically smallest set of indices.
InputThe first line of the standard input contains two space-separated integers N (2 <= N <= 800 000) and K (2 <= 2 * K <= N). The next line contains sequence of 0s and 1s of length N.
OutputTo the first line of the standard output you should print 2 * K indices (separated by a single space). If such set does not exist, you should print only one integer -1.
Input:
Output:
8 2
00100100Output:
2 3 4 5Explanation:
At position 2 and position 5 we have 1s. Note that indices are 0-based.
Input:
Output:
10 3
1000100000Output:
-1Input:
Output:
8 2
01111101Output:
0 1 2 6Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.