# 11840 - Moving books
>author: Utin
###### tags: `array`
---

## Brief
See the code below

## Solution 0

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

int N, book[26], shelf[26];

void pile_over(int from, int to);
void pile_onto(int from, int to);
void move_over(int from, int to);
void move_onto(int from, int to);

void print();
void print_value(int a);

void clean(int a);
void connect(int from, int to);

int check(int a, int b);

int main() {
    char op[10];
    int from, to;

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        book[i] = i;
        shelf[i] = i;
    }
    while (1) {
        scanf("%s", op);

        // exit
        if (!strcmp(op, "exit")) break;

        // pile
        else if (!strcmp(op, "pile")) {
            scanf("%d %s %d", &from, op, &to);
            if (from == to || check(from, to) || check(to, from)) continue;
            else if (!strcmp(op, "onto")) pile_onto(from, to);
            else if (!strcmp(op, "over")) pile_over(from, to);
        }

        // move
        else if (!strcmp(op, "move")) {
            scanf("%d %s %d", &from, op, &to);
            if (from == to || check(from, to) || check(to, from)) continue;
            else if (!strcmp(op, "onto")) move_onto(from, to);
            else if (!strcmp(op, "over")) move_over(from, to);
        }
    }

    // output
    print();
}

void pile_over(int from, int to) {
    connect(from, to);                    //connect from and to
}

void pile_onto(int from, int to) {
    clean(to);                            // clean to
    connect(from, to);                    // connect from and to
}

void move_over(int from, int to) {
    clean(from);                          // clean from
    while (to != book[to]) to = book[to]; // search the top book
    connect(from, to);                    // connect from and to
}

void move_onto(int from, int to) {
    clean(from);                          // clean from
    clean(to);                            // clean to
    connect(from, to);                    // connect from and to
}

void print() {
    for (int i = 0; i < N; i++) {
        printf("%d:", i);
        if (shelf[i] != -1) print_value(shelf[i]);
        printf("\n");
    }
}

void print_value(int a) {
    printf(" %d", a);
    if (a != book[a]) print_value(book[a]);
}

void clean(int a) {
    int curr = a;
    while (curr != book[curr]) {
        int tmp = curr;
        curr = book[curr];
        shelf[curr] = curr;
        book[tmp] = tmp;
    }
}

void connect(int from, int to) {
    book[to] = from;
    if (shelf[from] == -1) {
        for (int i = 0; i < N; i++) {
            if (book[i] == from && i != to) {
                book[i] = i;
                break;
            }
        }
    }
    else shelf[from] = -1;
}

int check(int a, int b) {
    while (a != book[a]) {
        a = book[a];
        if (a == b) return 1;
    }
    return 0;
}

// Utin

## Solution 1

#include <stdio.h>

typedef struct _book {
	int num;
	struct _book* next, * pre;
} Book;

Book shelf[25], book[25];

void init(int n);
void move_onto(int A, int B);
void move_over(int A, int B);
void pile_onto(int A, int B);
void pile_over(int A, int B);
void clean(int idx);
void connect(int A, int B);
void output(Book* book);
int err(int A, int B);

int main() {
    char op[5] = {0};
    int N, A, B;
    scanf("%d", &N);
    init(N);
    while (1) {
        scanf("%s", op);
        if (op[0] == 'e') break;
        else if (op[0] == 'm') {
            scanf("%d %s %d", &A, op, &B);
            if (err(A, B) || err(B, A)) continue;
            if (op[1] == 'n') move_onto(A, B);
            else move_over(A, B);
        }
        else {
            scanf("%d %s %d", &A, op, &B);
            if (err(A, B) || err(B, A)) continue;
            if (op[1] == 'n') pile_onto(A, B);
            else pile_over(A, B);
        }
    }
    for (int i = 0; i < N; i++) {
        printf("%d:", i);
        output(shelf[i].next);
        printf("\n");
    }
}

void init(int n) {
    for (int i = 0; i < n; i++) {
        shelf[i].next = &book[i];
        book[i].num = i;
        book[i].next = NULL;
        book[i].pre = &shelf[i];
    }
}

void move_onto(int A, int B) {
    clean(A);
    clean(B);
    connect(A, B);
}

void move_over(int A, int B) {
    clean(A);
    Book* curr = &book[B];
    while (curr->next) curr = curr->next;
    connect(A, curr->num);
}

void pile_onto(int A, int B) {
    clean(B);
    connect(A, B);
}
void pile_over(int A, int B) {
    Book* curr = &book[B];
    while (curr->next) curr = curr->next;
    connect(A, curr->num);
}

void clean(int idx) {
    Book* curr = &book[idx];
    while (curr->next) {
        curr = curr->next;
        curr->pre->next = NULL;
        shelf[curr->num].next = curr;
        curr->pre = &shelf[curr->num];
    }
}

void connect(int A, int B) {
    book[B].next = &book[A];
    book[A].pre->next = NULL;
    book[A].pre = &book[B];
}

void output(Book* book) {
    while (book) {
        printf(" %d", book->num);
        book = book->next;
    }
}

int err(int A, int B) {
    Book* curr = &book[A];
    while (curr) {
        if (curr->num == B) return 1;
        curr = curr->next;
    }
    return 0;
}

// Utin

## Reference