Thieves and Prisons

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;

public class brute {

    public static boolean isInPrison(int thief_prisonIndex) {
        return thief_prisonIndex != -1;
    }

    public static boolean isOpenValid(int[] thieves, int thief, int tentativePrison) {
        boolean prisonEmpty = true;
        for (int i = 0; i < thieves.length; i++) {
            if (thieves[i] == tentativePrison) {
                prisonEmpty = false;
                break;
            }
        }
        if (prisonEmpty) {
            return false;
        }
        return true;
    }

    public static class Event {
        boolean type; // false = C, true = O
        int thief;
        int prison;

        public Event(boolean type, int thief) {
            this.type = type;
            this.thief = thief;
            this.prison = -1;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = Integer.parseInt(scanner.next());
        int k = Integer.parseInt(scanner.next());
        int m = Integer.parseInt(scanner.next());

        Event[] events = new Event[m];
        for (int i = 0; i < m; i++) {
            boolean type = scanner.next().contains("O");
            int thief = Integer.parseInt(scanner.next());
            events[i] = new Event(type, thief);
        }

        // backtracking algorithm
        
        boolean possible = true;

        int[] thieves = new int[n];
        Arrays.fill(thieves, -1);

        ArrayList<int[]> history = new ArrayList<>();
        history.add(thieves);

        int index = 0;

        while (true) {
            if (index >= events.length) {
                break;
            }

            if (index < 0) {
                possible = false;
                break;
            }

            int[] curThieves = history.get(history.size() - 1);
            Event curEvent = events[index];

            curEvent.prison++;
            if (curEvent.prison >= k || // we have exhausted all possible configurations
                    isInPrison(curThieves[curEvent.thief - 1])) { // thief is in prison, can't take an action
                // backtrack
                curEvent.prison = -1;
                history.remove(history.size() - 1);
                index--;
                continue;
            }

            if (events[index].type == false) { // a thief has been caught
                // catch the thief
                int[] nextThieves = curThieves.clone();
                nextThieves[curEvent.thief - 1] = curEvent.prison;
                history.add(nextThieves);
                index++;
            } else { // a thief has opened a gate
                if (isOpenValid(curThieves, curEvent.thief - 1, curEvent.prison)) {
                    int[] nextThieves = curThieves.clone();
                    // free all prisoners
                    for (int i = 0; i < nextThieves.length; i++) {
                        if (nextThieves[i] == curEvent.prison) {
                            nextThieves[i] = -1;
                        }
                    }
                    history.add(nextThieves);
                    index++;
                    continue;
                } else {
                    // illegal action
                    continue;
                }
            }
        }

        if (possible) {
            String outStr = "";
            for (int i = 0; i < events.length; i++) {
                outStr += (events[i].prison + 1) + " ";
                // System.out.println(events[i].prison + 1);
            }
            System.out.println(outStr);
        } else {
            System.out.println("IMPOSSIBLE");
        }

        scanner.close();
    }
}

Test 1

Group: 2, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 4, 5

Verdict: ACCEPTED

Test 3

Group: 2, 4, 5

Verdict: ACCEPTED

Test 4

Group: 2, 4, 5

Verdict: ACCEPTED

Test 5

Group: 2, 4, 5

Verdict: ACCEPTED

Test 6

Group: 4, 5

Verdict: ACCEPTED

Test 7

Group: 4, 5

Verdict: ACCEPTED

Test 8

Group: 4, 5

Verdict: ACCEPTED

Test 9

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 13

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 14

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 15

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 16

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 17

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 18

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 19

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3, 4, 5

Verdict: ACCEPTED

Test 25

Group: 3, 4, 5

Verdict: ACCEPTED

Test 26

Group: 3, 4, 5

Verdict: ACCEPTED

Test 27

Group: 3, 4, 5

Verdict: ACCEPTED

Test 28

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 2, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 2, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 2, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 2, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 42

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 47

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED