Family Crisis Solver

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.Collectors;
 
/**
 * Created: 10/9/22
 * Author: thucdx
 **/
class FamilyCrisis {
    static boolean DEBUG = true;
    static boolean IS_LOCAL = null != System.getenv("LOCAL_JUDGE");
 
    static class Pair implements Comparable<Pair> {
        long state;
        int time;
 
        public Pair(long state, int step) {
            this.state = state;
            this.time = step;
        }
 
        @Override
        public int compareTo(Pair o) {
            return time - o.time;
        }
    }
 
    static class FamilyCrisisSolver {
        int n;
        int[] times;
        Map<Long, Integer> minStep;
        Map<Long, Long> prev;
 
        static int INF = (int) 1e9;
 
        private static boolean getBit(long state, int k) {
            return (state & (1L << k)) > 0;
        }
 
        private static List<Integer> getOnBit(long state, int minId, int maxId) {
            List<Integer> result = new ArrayList<>();
            for (int i = minId; i < maxId; i++) {
                if (getBit(state, i))  {
                    result.add(i);
                }
            }
            return result;
        }
 
        private static long setBit(long state, int k) {
            return state | (1L << k);
        }
 
        private static long reverseBit(long state, int k) {
            return state ^ (1L << k);
        }
 
        public FamilyCrisisSolver(int[] times) {
            this.times = times;
            this.n = times.length;
        }
 
        public List<Pair> nextState(Pair cur) {
            List<Pair> possibleStates = new ArrayList<>();
            boolean hasLamp = getBit(cur.state, n);
            List<Integer> bitOn = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (getBit(cur.state, i) == hasLamp) {
                    bitOn.add(i);
                }
            }
//            debug("cur state", cur.state);
//            debug(bitOn);
 
            if (hasLamp) {
                // choose up to 2 people
                for (int i = 0; i < bitOn.size(); i++) {
                    for (int j = i + 1; j < bitOn.size(); j++) {
                        long state = cur.state;
                        state = reverseBit(state, bitOn.get(i));
                        state = reverseBit(state, bitOn.get(j));
 
                        // hasLamp = false
                        state = reverseBit(state, n);
                        int totalTime = cur.time + Math.max(times[bitOn.get(i)], times[bitOn.get(j)]);
 
//                        debug("i, j, state, totalTime, curState: ", bitOn.get(i), bitOn.get(j), state, totalTime, cur.state);
                        possibleStates.add(new Pair(state, totalTime));
                    }
                }
            } else {
                // Choose 1 person to bring lamp
                for (Integer bitNum : bitOn) {
                    long state = cur.state;
                    state = reverseBit(state, bitNum);
                    state = reverseBit(state, n);
                    int totalTime = cur.time + times[bitNum];
                    possibleStates.add(new Pair(state, totalTime));
                }
            }
 
            return possibleStates;
        }
 
        public int solve() {
            int n = times.length;
            // state = n+1 bits,
            // has_lamp, person_0, person_1, .... person_n-1
            long start = (1L << (n + 1)) - 1;
            long endState = 0;
 
            minStep = new HashMap<>();
            prev = new HashMap<>();
            Queue<Pair> q = new PriorityQueue<>();
            q.add(new Pair(start, 0));
            minStep.put(start, 0);
 
            while (!q.isEmpty()) {
                Pair cur = q.poll();
 
                if (cur.state == endState) {
                    List<Long> transitionStates = new ArrayList<>();
                    Long curState = cur.state;
                    do {
                        transitionStates.add(curState);
                        curState = prev.get(curState);
                    } while (curState != null);
                    Collections.reverse(transitionStates);
                    Writer writer = new OutputStreamWriter(System.out);
                    try {
                        printResult(transitionStates, cur.time, writer);
                        writer.flush();
                    } catch (IOException e) {
                        throw new RuntimeException(e);
                    }
 
                    return cur.time;
                }
 
                List<Pair> possibleStates = nextState(cur);
                for (Pair possibleState : possibleStates) {
                    if (minStep.getOrDefault(possibleState.state, INF) > possibleState.time) {
                        prev.put(possibleState.state, cur.state);
                        q.add(possibleState);
                        minStep.put(possibleState.state, possibleState.time);
                    }
                }
            }
 
            return -1;
        }
 
        public void printResult(List<Long> transitionStates, int totalTime, Writer writer) throws IOException {
            writer.write("Finish in " + totalTime + " time units\n");
            for (int i = 1; i < transitionStates.size(); i++) {
                StringBuilder cmd = new StringBuilder("Move ");
                Long diff = transitionStates.get(i) ^ transitionStates.get(i-1);
                List<Integer> onBits = FamilyCrisisSolver.getOnBit(diff, 0, n);
                cmd.append(onBits.stream().map(id -> "#" + id + " ").collect(Collectors.joining("and ")));
                cmd.append("from ").append(FamilyCrisisSolver.getBit(transitionStates.get(i), n) ? "left to right" : "right to left");
                writer.write(cmd + "\n");
            }
        }
    }
 
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            if (IS_LOCAL) {
                br = new BufferedReader(new InputStreamReader(Files.newInputStream(Paths.get("input/FamilyCrisis.inp"))));
            }
            FastReader fr = new FastReader(br);
 
            int n = fr.nextInt();
            int[] times = new int[n];
            for (int i = 0; i < n; i++) {
                times[i] = fr.nextInt();
            }
            Arrays.sort(times);
 
            FamilyCrisisSolver solver = new FamilyCrisisSolver(times);
            int time = solver.solve();
        } catch (Exception ex) {
            System.out.println(ex.getMessage());
            ex.printStackTrace();
        }
    }
 
    static void debug(List<Object> args) {
         if (IS_LOCAL && DEBUG) {
            System.out.println("\t[DEBUG] " + args.stream().map(Object::toString).collect(Collectors.joining(", ")));
        }
    }
 
    static void debug(Object... args) {
        if (IS_LOCAL && DEBUG) {
            System.out.println("\t[DEBUG] " + Arrays.stream(args).map(Object::toString).collect(Collectors.joining(", ")));
        }
    }
 
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader() {
            br = new BufferedReader(
                    new InputStreamReader(System.in));
        }
 
        public FastReader(BufferedReader br) {
            this.br = br;
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                if (st.hasMoreTokens()) {
                    str = st.nextToken("\n");
                } else {
                    str = br.readLine();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
 
}