GCJ2015-C-Small

gistfile1.java

package gcj2015;

import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class C {
    private static final int CACHE_SIZE = 8;
    public static final short ONE = 1;
    public static final short I = 2;
    public static final short J = 4;
    public static final short K = 8;
    public static final short N_ONE = 16 + 1;
    public static final short N_I = 16 + 2;
    public static final short N_J = 16 + 4;
    public static final short N_K = 16 + 8;

    static short[][] dots = new short[][] {
            new short[] {ONE,     I,     J,     K},
            new short[] {  I, N_ONE,     K,   N_J},
            new short[] {  J,   N_K, N_ONE,     I},
            new short[] {  K,     J,   N_I, N_ONE}
    };

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(new FileReader(args[0]));
        FileWriter writer = new FileWriter(args[1]);
        int t = scanner.nextInt();
        for ( int i = 1; i <= t; i++) {
            long l = scanner.nextLong();
            long x = scanner.nextLong();
            String s = scanner.next();

            String resultOutput = String.format("Case #%d: %s", i, Program.run(l,x,s) ? "YES" : "NO");
            System.out.println(resultOutput);

            writer.append(resultOutput);
            writer.append("\n");
        }
        writer.close();
    }

    public static class Program {

        // 1 -> 00001
        // i -> 00010
        // j -> 00100
        // k -> 01000
        // -1 -> 10001
        // -i -> 10010
        // -j -> 10100
        // -k -> 11000

        public static String makeString(long l, long x, String chars) {
            long i = x;
            String s = "";
            while(i-- > 0) s += chars;

            return s;
        }

        public static boolean satisfy(String s) {
            short l = ONE; //q(s.charAt(0));
            for(int i = 0; i < s.length() - 1; i++) {
                l = multiply(l, q(s.charAt(i))); //reduce(s.substring(0, i));
                if (l != I) continue;


                short m = ONE; //q(s.charAt(i + 1));
                short r = reduce(s.substring(i + 2));
                for ( int j = i + 1; j < s.length() - 1; j++) {
                    m = multiply(m, q(s.charAt(j)));
                    if (m == J && r == K) return true;

                    short x = invert(q(s.charAt(j + 1)));
                    r = multiply(x,r);
                }
            }
            return false;
        }

        private static short invert(short q) {
            if (q == I) return N_I;
            if (q == J) return N_J;
            if (q == K) return N_K;
            return ONE;
        }

        private static final Map<String, Short> cache = new HashMap();
        private static void rec(String s, short a, int c) {
            if (c == 0) return;

            String key1 = s + "i";
            short ret1 = multiply(a, I);
            cache.put(key1, ret1);
            rec(key1, ret1, c - 1);

            String key2 = s + "j";
            short ret2 = multiply(a, J);
            cache.put(key2, ret2);
            rec(key2, ret2, c - 1);

            String key3 = s + "k";
            short ret3 = multiply(a, K);
            cache.put(key3, ret3);
            rec(key3, ret3, c - 1);
        }

        static {
            cache.clear();
            rec("", ONE, CACHE_SIZE);
        }

        public static short reduce(String s) {
            if(s.isEmpty()) return ONE;
            if(s.length() < CACHE_SIZE) return cache.get(s);

            short a = reduce(s.substring(0, (s.length() / 2)));
            short b = reduce(s.substring((s.length() / 2)));
            //System.out.println((lhs + rhs).equals(s) ? "ok" : "ng");
            return multiply(a,b);
        }

        public static boolean run(long l, long x, String s) {
            if ( l * x < 3) {
                return false;
            }
            x = x % (4 * l);

            String ss = Program.makeString(l, x, s);
            return satisfy(ss);
        }

        public static short q(char c) {
            switch (c) {
                case 'i':
                    return I;
                case 'j':
                    return J;
                case 'k':
                    return K;
            }
            return 0;
        }
        public static int binaryIndex(int a) {
            for(int i = 0; i < 4; i++) {
                if (((a >> i) & 1) > 0) return i;
            }
            return -1;
        }

        public static short multiply(short a, short b) {
            final int mask = 15;
            short sign = (short)((a & 16) ^ (b & 16));
            short x = dots[binaryIndex(a & mask)][binaryIndex(b & mask)];
            return (short)(x ^ sign);
        }
    }
}