4277. Block reversal

Given a single chain table L, We will every K A node is regarded as a block （ If the linked list is insufficient at the end K Nodes , Also as a block ）, Please write a program to L The links of all blocks in are reversed .

for example ： Given L by 1→2→3→4→5→6→7→8,K by 3, Then the output should be 7→8→4→5→6→1→2→3.

Add
This question may contain nodes that are not in the single linked list , These nodes need not be considered .

Input format

The first 1 Line gives 1 The address of the node 、 The total number of nodes is a positive integer N、 And positive integers K, That is, the size of the block . The address of the node is 5 Bit nonnegative integer （ May contain leading 0）,NULL Address use −1−1 Express .

Next there is N That's ok , The format of each line is ：

Address Data Next

among Address Is the node address ,Data Is the integer data saved in this node ,Next Is the address of the next node .

Output format

For each test case , Output the inverted linked list in sequence , Each node on it occupies a row , The format is the same as the input .

Data range

1≤K≤N≤105

sample input ：

00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218

sample output ：

71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1

Code ：

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, k;
int h, e[N], ne[N];

int main()
{
    
    scanf("%d%d%d", &h, &n, &k);

    for (int i = 0; i < n; i++)
    {
    
        int address, data, next;
        scanf("%d%d%d", &address, &data, &next);
        e[address] = data, ne[address] = next;
    }

    vector<int> q;
    for (int i = h; i != -1; i = ne[i])
        q.push_back(i);
    int size = q.size() % k; //  This step must be thought clearly , The remainder is redundant data 
    // size / k  How many do you have block
    reverse(q.begin(), q.end());
    bool flag = true;
    for (int i = 0; i < q.size();)
    {
    
        if (flag)
            reverse(q.begin() + i, q.begin() + i + size), i += size, flag = false;
        else
        {
    
            reverse(q.begin() + i, q.begin() + i + k);
            i += k;
        }
    }
    for (int i = 0; i < q.size(); i++)
    {
    
        printf("%05d %d ", q[i], e[q[i]]);
        if (i + 1 == q.size())
            puts("-1");
        else
            printf("%05d\n", q[i + 1]);
    }

    return 0;
}