Submission #1197786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197786		ahmedafeef	Knjige (COCI20_knjige)	C11	0 / 50	0 ms	324 KiB

Main

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

#define MAX_N 100

typedef struct {
    char instruction[5]; // "UZMI" or "STAVI"
    char hand;          // 'L' or 'D'
    char shelf;         // 'L' or 'D'
} Move;

Move moves[100000];
int move_count = 0;

void add_move(const char* instruction, char hand, char shelf) {
    Move m;
    sprintf(m.instruction, "%s", instruction);
    m.hand = hand;
    m.shelf = shelf;
    moves[move_count++] = m;
}

int main() {
    int n;
    int d[MAX_N];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &d[i]);
    }

    // Check if already sorted
    int sorted = 1;
    for (int i = 0; i < n - 1; ++i) {
        if (d[i] > d[i+1]) {
            sorted = 0;
            break;
        }
    }
    if (sorted) {
        printf("0\n");
        return 0;
    }

    // Simulate the left and right shelves
    int left_top = 0;
    int left_stack[MAX_N];
    int left_size = n;
    for (int i = 0; i < n; ++i) {
        left_stack[i] = d[i];
    }

    int right_stack[MAX_N];
    int right_size = 0;

    int hand_L = -1; // -1 means empty
    int hand_R = -1;

    while (1) {
        // Check if left stack is sorted
        sorted = 1;
        for (int i = 0; i < left_size - 1; ++i) {
            if (left_stack[i] > left_stack[i+1]) {
                sorted = 0;
                break;
            }
        }
        if (sorted && right_size == 0) {
            break;
        }

        // Find the smallest element in left stack
        if (left_size == 0) {
            // Move all from right to left
            while (right_size > 0) {
                if (hand_L == -1) {
                    add_move("UZMI", 'L', 'D');
                    hand_L = right_stack[right_size - 1];
                    right_size--;
                } else if (hand_R == -1) {
                    add_move("UZMI", 'D', 'D');
                    hand_R = right_stack[right_size - 1];
                    right_size--;
                } else {
                    // Need to free a hand
                    add_move("STAVI", 'L', 'L');
                    left_stack[left_size++] = hand_L;
                    hand_L = -1;
                }
            }
            if (hand_L != -1) {
                add_move("STAVI", 'L', 'L');
                left_stack[left_size++] = hand_L;
                hand_L = -1;
            }
            if (hand_R != -1) {
                add_move("STAVI", 'D', 'L');
                left_stack[left_size++] = hand_R;
                hand_R = -1;
            }
            continue;
        }

        int min_pos = 0;
        for (int i = 1; i < left_size; ++i) {
            if (left_stack[i] < left_stack[min_pos]) {
                min_pos = i;
            }
        }

        // Move books above min_pos to right shelf
        for (int i = 0; i < left_size - min_pos - 1; ++i) {
            if (hand_L == -1) {
                add_move("UZMI", 'L', 'L');
                hand_L = left_stack[left_size - 1];
                left_size--;
            } else if (hand_R == -1) {
                add_move("UZMI", 'D', 'L');
                hand_R = left_stack[left_size - 1];
                left_size--;
            } else {
                // Need to free a hand by putting one book to right
                add_move("STAVI", 'L', 'D');
                right_stack[right_size++] = hand_L;
                hand_L = -1;
            }
        }

        // Take the min book
        if (hand_L == -1) {
            add_move("UZMI", 'L', 'L');
            hand_L = left_stack[left_size - 1];
            left_size--;
        } else if (hand_R == -1) {
            add_move("UZMI", 'D', 'L');
            hand_R = left_stack[left_size - 1];
            left_size--;
        } else {
            add_move("STAVI", 'L', 'D');
            right_stack[right_size++] = hand_L;
            hand_L = -1;
            add_move("UZMI", 'L', 'L');
            hand_L = left_stack[left_size - 1];
            left_size--;
        }

        // Put the min book to the left shelf (but it's now empty)
        // So first, move all books from right shelf back to left
        while (right_size > 0) {
            if (hand_R == -1) {
                add_move("UZMI", 'D', 'D');
                hand_R = right_stack[right_size - 1];
                right_size--;
            } else if (hand_L == -1) {
                add_move("UZMI", 'L', 'D');
                hand_L = right_stack[right_size - 1];
                right_size--;
            } else {
                add_move("STAVI", 'D', 'L');
                left_stack[left_size++] = hand_R;
                hand_R = -1;
            }
        }

        // Now place the min book
        if (hand_R != -1) {
            add_move("STAVI", 'D', 'L');
            left_stack[left_size++] = hand_R;
            hand_R = -1;
        }
        add_move("STAVI", 'L', 'L');
        left_stack[left_size++] = hand_L;
        hand_L = -1;

        // Move remaining books from right to left
        while (right_size > 0) {
            if (hand_L == -1) {
                add_move("UZMI", 'L', 'D');
                hand_L = right_stack[right_size - 1];
                right_size--;
            } else if (hand_R == -1) {
                add_move("UZMI", 'D', 'D');
                hand_R = right_stack[right_size - 1];
                right_size--;
            } else {
                add_move("STAVI", 'L', 'L');
                left_stack[left_size++] = hand_L;
                hand_L = -1;
            }
        }

        if (hand_L != -1) {
            add_move("STAVI", 'L', 'L');
            left_stack[left_size++] = hand_L;
            hand_L = -1;
        }
        if (hand_R != -1) {
            add_move("STAVI", 'D', 'L');
            left_stack[left_size++] = hand_R;
            hand_R = -1;
        }
    }

    printf("%d\n", move_count);
    for (int i = 0; i < move_count; ++i) {
        printf("%s %c %c\n", moves[i].instruction, moves[i].hand, moves[i].shelf);
    }

    return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:26:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
Main.c:28:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d", &d[i]);
      |         ^~~~~~~~~~~~~~~~~~
Main.c:17:31: warning: '__builtin___sprintf_chk' writing a terminating nul past the end of the destination [-Wformat-overflow=]
   17 |     sprintf(m.instruction, "%s", instruction);
      |                               ^
In file included from /usr/include/stdio.h:894,
                 from Main.c:1:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:38:10: note: '__builtin___sprintf_chk' output 6 bytes into a destination of size 5
   38 |   return __builtin___sprintf_chk (__s, __USE_FORTIFY_LEVEL - 1,
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   39 |                                   __glibc_objsize (__s), __fmt,
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 |                                   __va_arg_pack ());
      |                                   ~~~~~~~~~~~~~~~~~
Main.c:17:31: warning: '__builtin___sprintf_chk' writing a terminating nul past the end of the destination [-Wformat-overflow=]
   17 |     sprintf(m.instruction, "%s", instruction);
      |                               ^
In file included from /usr/include/stdio.h:894,
                 from Main.c:1:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:38:10: note: '__builtin___sprintf_chk' output 6 bytes into a destination of size 5
   38 |   return __builtin___sprintf_chk (__s, __USE_FORTIFY_LEVEL - 1,
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   39 |                                   __glibc_objsize (__s), __fmt,
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 |                                   __va_arg_pack ());
      |                                   ~~~~~~~~~~~~~~~~~
Main.c:17:31: warning: '__builtin___sprintf_chk' writing a terminating nul past the end of the destination [-Wformat-overflow=]
   17 |     sprintf(m.instruction, "%s", instruction);
      |                               ^
In file included from /usr/include/stdio.h:894,
                 from Main.c:1:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:38:10: note: '__builtin___sprintf_chk' output 6 bytes into a destination of size 5
   38 |   return __builtin___sprintf_chk (__s, __USE_FORTIFY_LEVEL - 1,
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   39 |                                   __glibc_objsize (__s), __fmt,
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 |                                   __va_arg_pack ());
      |                                   ~~~~~~~~~~~~~~~~~
Main.c:17:31: warning: '__builtin___sprintf_chk' writing a terminating nul past the end of the destination [-Wformat-overflow=]
   17 |     sprintf(m.instruction, "%s", instruction);
      |                               ^
In file included from /usr/include/stdio.h:894,
                 from Main.c:1:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:38:10: note: '__builtin___sprintf_chk' output 6 bytes into a destination of size 5
   38 |   return __builtin___sprintf_chk (__s, __USE_FORTIFY_LEVEL - 1,
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   39 |                                   __glibc_objsize (__s), __fmt,
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 |                                   __va_arg_pack ());
      |                                   ~~~~~~~~~~~~~~~~~
Main.c:17:31: warning: '__builtin___sprintf_chk' writing a terminating nul past the end of the destination [-Wformat-overflow=]
   17 |     sprintf(m.instruction, "%s", instruction);
      |                               ^
In file included from /usr/include/stdio.h:894,
                 from Main.c:1:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:38:10: note: '__builtin___sprintf_chk' output 6 bytes into a destination of size 5
   38 |   return __builtin___sprintf_chk (__s, __USE_FORTIFY_LEVEL - 1,
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   39 |                                   __glibc_objsize (__s), __fmt,
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 |                                   __va_arg_pack ());
      |                                   ~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 50