Divide and Maximize

3.1

12 votes
Sorting, Probablity, random, maximization, approximate, Basic Probability, Mathematics, Medium-Hard
Problem

You are given an integer array A of length 2N and integer K. Your should divide this array onto two arrays B and C with such rules:

  1. The sizes of arrays B and C are equal to N.
  2. Each element of array A belongs to exactly one of the arrays B or C.
  3. Arrays B and C store indices of selected elements.
  4. You must maintain the relative order of the elements (arrays B and C must be sorted by ascending).
  5. You can't take K consecutive indices in either of two arrays. (for example if K is equal to 3, then you can't take indices [5,6,7] into arrays B or C).

Your task is to maximize the following value: Ni=1f(ABi,ACi), where f(x,y) is equal to 1 if x<y and 0 otherwise.

Input format:

First line contains two space-separated integers N (1N5104) and K (2Kmin(2N,100)).

Next line contains 2N space-separated integers denoting the array A (1Ai109).

Output format:

In a first line output N space-separated integers denoting array B.

In a second line output N space-separated integers denoting array C.

Verdict and scoring:

Your score is equal to the sum of the values of all test cases.

The value of each test is calculated using this formula: Ni=1f(ABi,ACi), where f(x,y) is equal to 1 if x<y and 0 otherwise.

If at least one of the rules will be violated, then your value for this test will be 0.

Test generation plan:

Each test has own upper bound Z (1Z109), denoting that every Ai in this test is not exceeding Z.

In each test N and K are randomly generated (considering constraints), Z is not randomly generated.

In 38% tests: all elements of array A are randomly generated (considering constraints and limit Z).

In all other tests: while the current amount of written elements is not equal to 2N do:

  • take two randomly generated positive integers X (considering constraints and limit Z) and Y
  • Y times write number X (guaranteed that the current amount of written elements plus Y is less than or equal to 2N)

 

Sample Input
4 3
1 2 2 4 3 2 4 2
Sample Output
1 3 6 7
2 4 5 8
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

Elements of array A corresponding to indices of array B[1,2,2,4].

Elements of array A corresponding to indices of array C[2,4,3,2].

In this case the score is equal to f(1,2)+f(2,4)+f(2,3)+f(4,2)=1+1+1+0=3.

Editor Image

?