50128. Split a List

I'm a slow walker, but I never walk backwards.

Task Description

We have two arrays $A$ and $a$. The elements of $A$ are positive integers, and the elements of $a$ are pointers to integer. We initialize a so that $a\lbrack i]$ pointing to the $A\lbrack i+1]$, and the last element of $a$ is NULL. This is like a list of integers. Please refer to the following figure.

samplesample

Now we want to split this list of integers into $k$ lists. We have a pointer array of $k$ elements ($head$) as the the heads of these $k$ lists. The list of $A$ is split into $k$ lists according to the remainder when divided by $k$. That is, all integers of $A$ in the form as $\lbrace kn\rbrace $ will be in the first list, and those as $\lbrace kn+1\rbrace $ will be in the second list, and so on. Please refer to the following figure for an illustration. For example, we have $k = 5$ and the first list (starting from $head\lbrack 0]$) will have $35$ (in $A\lbrack 1]$) and $65$ (in $A\lbrack 4]$). Note that there is no element after $65$ so $a\lbrack 4]$ will be NULL. Also note that if there are no elements in a list, the corresponding $head$ will be NULL. For example, no element in $A$ is $5n + 3$, so $head\lbrack 3]$ is NULL.

samplesample
Write a function split to split the elements in $A$ into $k$ lists as described above.

The prototype of split.h is as follows. (Remember to include stdlib.h in split.c.)

void split(int A[], int *a[], int *head[], int k);

You can use the following main.c to test your function.

#include <stdio.h>
#include <stdlib.h>
#include "split.h"
 
int main(int argc, char const *argv[])
{
    int N, k;
    scanf("%d%d", &N, &k);
    int A[N];
    for (int i = 0; i < N; ++i)
        scanf("%d", &A[i]);
    int *a[N], *head[k];
    for (int i = 0; i < N-1; ++i)
        a[i] = &A[i+1];
    a[N-1] = NULL;
    for (int i = 0; i < k; ++i)
        head[i] = NULL;
    split(A, a, head, k);
    for (int i = 0; i < k; ++i) {
        if (head[i] == NULL)
            printf("NULL\n");
        else {
            int *tmp = head[i];
            printf("%d", *tmp);
            tmp = *(tmp-A+a);
            while (tmp != NULL) {
                printf(" %d", *tmp);
                tmp = *(tmp-A+a);
            }
            printf("\n");
        }
    }
    return 0;
}

Input Format (for the test main program)

We will give you $A$, $a$, $head$, and $k$ as the input of function split. $A$ and $a$ have the same size $N$. The size of $head$ is $k$. For main.c, the input will be $N$, $k$ in the first line, and elements of array $A$ in the second line.

  • $1\leq N \lt 100000$
  • $1\leq k \lt 100000$

Output Format (for the test main program)

For main.c, the output has $k$ lines representing $k$ lists from $\lbrace kn\rbrace $ to $\lbrace kn+(k-1)\rbrace $. Each line shows elements in one list according to the pointing order. If there is no element in a list, that line will output NULL.

Hint

It is more convenient to use an array $tail$ to record the current last integer of each list.

Subtasks

  • 10 points: $k$ is 1.
  • 30 points: $k$ is 2.
  • 60 points: $k$ is larger than 2.

Sample Input

10 5
14 35 4 66 65 17 79 59 22 86

Sample Output

35 65
66 86
17 22
NULL
14 4 79 59

Discussion