BOJ. Set (11723)

Bitmask

The set contains only the integers 1 through 20, so store membership in one int. Map value x to bit position x - 1: 1 << (x - 1) creates a mask with exactly that bit set. Shifts are zero-based, which is why the value must be decremented. The full-set mask is (1 << 20) - 1, whose low 20 bits are all 1; 0 represents the empty set.

For add, OR the mask into the set; for remove, AND with its complement; for check, AND and test for a nonzero result; and for toggle, XOR. all assigns the full mask, while empty clears it. The input guarantees each value command uses 1 <= x <= 20; add and remove are safe even when membership is already in the requested state. Each command takes O(1) time and the set uses O(1) space.

Problem link

Java

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    private static final int FULL_SET = (1 << 20) - 1;

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int commandCount = input.nextInt();
        int set = 0;
        StringBuilder output = new StringBuilder();

        for (int i = 0; i < commandCount; i++) {
            String command = input.next();
            if (command.equals("all")) {
                set = FULL_SET;
            } else if (command.equals("empty")) {
                set = 0;
            } else {
                int x = input.nextInt();
                int mask = 1 << (x - 1);
                switch (command) {
                    case "add":
                        set |= mask;
                        break;
                    case "remove":
                        set &= ~mask;
                        break;
                    case "check":
                        output.append((set & mask) != 0 ? 1 : 0).append('\n');
                        break;
                    case "toggle":
                        set ^= mask;
                        break;
                }
            }
        }

        System.out.print(output);
    }

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int length;
        private int position;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[position++];
        }

        String next() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            StringBuilder token = new StringBuilder();
            while (c > ' ') {
                token.append((char) c);
                c = read();
            }
            return token.toString();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}