# 10222. Split a List

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

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.

sample

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.

sample
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.

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

## Sample Input

10 514 35 4 66 65 17 79 59 22 86


## Sample Output

35 6566 8617 22NULL14 4 79 59