Thieves and Prisons

Note: input/Thieves_and_Prisons_v3.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

//just checking all combis to get some points
// it will get stack overflow

public class Thieves_and_Prisons_v3 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static boolean impossible = true;
    private static ArrayList<Integer> solution;
    private static String[] inputs;

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        int N = Integer.valueOf(input[0]);
        int K = Integer.valueOf(input[1]);
        int M = Integer.valueOf(input[2]);
        //HashSet<Character> thieves = new HashSet<>();
        ArrayList<HashSet> prisons = new ArrayList<HashSet>();
        for(int i = 0; i < K; i++) prisons.add(new HashSet<>());
        inputs = new String[M];
        for(int i = M-1; i >= 0; i--) {
            inputs[i] = br.readLine();
        }
        rec(M-1, prisons, new ArrayList<>(), new boolean[N+1]);
        if(!impossible){
            for(int i = 0; i < solution.size(); i++){
                System.out.print(Integer.toString(solution.get(i)) + (i == solution.size()-1 ? "" : " "));
            }
        }else{
            System.out.print("IMPOSSIBLE");
        }
    }

    private static boolean rec(int m, ArrayList<HashSet> prisons, ArrayList<Integer> changes, boolean[] thieves) throws IOException {
        if(m == -1){
            impossible = false;
            solution = changes;
            return true;
        }
        String[] input = inputs[m].split(" ");
        if(input[0].equals("C")){
            for(int i = 0; i < prisons.size(); i++){
                if(!prisons.get(i).contains(input[1]) && !thieves[Integer.valueOf(input[1])]){
                    ArrayList<HashSet> copy = new ArrayList<>();
                    for(int j = 0; j < prisons.size(); j++) copy.add(new HashSet(prisons.get(j)));
                    copy.get(i).add(input[1]);
                    ArrayList<Integer> copy_2 = new ArrayList<>(changes);
                    copy_2.add(i+1);
                    boolean[] copy_3 = Arrays.copyOfRange(thieves, 0, thieves.length);
                    copy_3[Integer.valueOf(input[1])] = true;
                    boolean temp = rec(m - 1, copy, copy_2, copy_3);
                    if(temp){
                        return temp;
                    }
                }
            }
        }else{
            for(int i = 0; i < prisons.size(); i++){
                if(prisons.get(i).size() != 0 && !thieves[Integer.valueOf(input[1])]){
                    ArrayList<HashSet> copy = new ArrayList<>();
                    for(int j = 0; j < prisons.size(); j++) copy.add(new HashSet(prisons.get(j)));
                    copy.set(i, new HashSet());
                    ArrayList<Integer> copy_2 = new ArrayList<>(changes);
                    copy_2.add(i+1);
                    boolean[] copy_3 = Arrays.copyOfRange(thieves, 0, thieves.length);
                    ArrayList<String> prisoners = new ArrayList<>(prisons.get(i));
                    for(int j = 0; j < prisoners.size(); j++){
                        copy_3[Integer.valueOf(prisoners.get(j))] = false;
                    }
                    boolean temp = rec(m - 1, copy, copy_2, copy_3);
                    if(temp){
                        return temp;
                    }
                }
            }
        }
        return false;
    }
}

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