How do i...solve this question

See more:

C++

Specifically, Billy's N kids are tagged with ID numbers 1...N.

Billy wants to take a picture of the kids standing in a line in a very specific ordering, represented by the contents of an array A[1...N], where A[j] gives the ID number of the jth kid in the ordering.

He arranges the kids in this order, but just before he can press the button on his camera to snap the picture, up to one kid moves to a new position in the lineup.

More precisely, either no kids move, or one kid vacates her current position in the lineup and then re-inserts herself at a new position in the lineup.

Frustrated but not deterred, Billy again arranges his kids according to the ordering in A, but again, right before he can snap a picture, up to one kid (different from the first) moves to a new position in the lineup.

The process above repeats for a total of five photographs before Billy gives up.

Given the contents of each photograph, see if you can reconstruct the original intended ordering A. Each photograph shows an ordering of the kids in which up to one kid has moved to a new location, starting from the initial ordering in A.

Moreover, if a kid opts to move herself to a new location in one of the photographs, then that kid does not actively move in any of the other photographs (although that kid can end up at a different position due to other kids moving, of course).


Input

First line has a single integer

Next 5N lines describe 5 orderings, each one a block of N contiguous lines.

Each line contains the ID of a kid, an integer in the range 1 <= id <= 1000000000

1 <= N <= 20,000


Output

In N lines, print the intended ordering of A, one ID per line.


Examples:

Input
5
10
20
30
40
50
20
10
30
40
50
30
10
20
40
50
40
10
20
30
50
50
10
20
30
40
Output
10
20
30
40
50
Input
2
1
2
2
1
1
2
2
1
2
1
Output
2
1

What I have tried:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_KIDS 20000
#define MAX_ID 1000000000

// Structure to represent each kid and their count
typedef struct {
    int id;
    int count;
} KidCount;

// Comparison function for sorting KidCount
int compare(const void *a, const void *b) {
    KidCount *kid1 = (KidCount *)a;
    KidCount *kid2 = (KidCount *)b;
    
    if (kid1->count != kid2->count) {
        return kid2->count - kid1->count; // Sort by count (descending)
    }
    return kid1->id - kid2->id; // Sort by id (ascending)
}

int main() {
    int N;
    scanf("%d", &N);
    
    int positions[5][MAX_KIDS]; // To store the IDs in each photograph
    int kid_pos[MAX_KIDS] = {0}; // To store the counts of IDs

    // Read all the photographs
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &positions[i][j]);
        }
    }

    // To determine the intended order
    KidCount counts[MAX_KIDS]; // To hold counts for each kid
    int id_index = 0; // To track the number of unique IDs

    // Collect counts for each position
    for (int j = 0; j < N; j++) {
        memset(counts, 0, sizeof(counts)); // Reset counts for this position
        id_index = 0; // Reset index

        // Collect IDs across all photographs for this position
        for (int i = 0; i < 5; i++) {
            int kid_id = positions[i][j];
            int found = 0;

            // Update counts
            for (int k = 0; k < id_index; k++) {
                if (counts[k].id == kid_id) {
                    counts[k].count++;
                    found = 1;
                    break;
                }
            }

            // If not found, add new ID to counts
            if (!found) {
                counts[id_index].id = kid_id;
                counts[id_index].count = 1;
                id_index++;
            }
        }

        // Sort the counts to find the most frequent ID
        qsort(counts, id_index, sizeof(KidCount), compare);
        
        // The most frequent ID for this position
        printf("%d\n", counts[0].id);
    }

    return 0;
}