Submission #1114184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114184		lyis	Snake Escaping (JOI18_snake_escaping)	Java	100 / 100	934 ms	65536 KiB

snake_escaping

import java.io.*;
import java.util.*;

public class snake_escaping {
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		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()); }
	}

	public static class Pair implements Comparable<Pair> {
		int vtx;
		int val;
		public Pair(int a, int b) {
			this.vtx = a;
			this.val = b;
		}
		public int compareTo(Pair other) {
			if (this.val < other.val) return -1;
			if (this.val > other.val) return 1;
			if (this.vtx < other.vtx) return -1;
			return 1;
		}
	}
	static int MOD = 998244353;

	public static void main(String[] args) {
		FastReader br = new FastReader();
		int L = br.nextInt();
		int Q = br.nextInt();
		final int[] S = new int[1 << L];
		final int[] sup = new int[1 << L];
		final int[] sub = new int[1 << L];
		final int[] btcnt = new int[1 << L];  // Precompute bitcount to speed up
		String s = br.next();
		for (int i = 0; i < (1 << L); i++) {
			S[i] = (int)s.charAt(i) - '0';
			sup[i] = sub[i] = S[i];
			btcnt[i] = Integer.bitCount(i);
		}
		// SOS DP!!
		for (int b = 0; b < L; b++) {
			for (int m = 0; m < (1 << L); m++) {
				if (((m >>> b) & 1) == 0) {
					sup[m] += sup[m ^ (1 << b)];
				} else {
					sub[m] += sub[m ^ (1 << b)];
				}
			}
		}

		StringBuilder sb =
		    new StringBuilder();  // I'm using stringbuilder to reduce the
		                          // number of times I print because calling
		                          // System.out.println 10^6 times is slow

		int A;
		int B;
		int C;
		int ca;
		int cb;
		int cc;
		long ans;
		for (int i = 0; i < Q; i++) {
			s = br.next();
			A = 0;
			B = 0;
			C = 0;
			ca = 0;
			cb = 0;
			cc = 0;
			ans = 0;
			for (int j = 0; j < L; j++) {
				if (s.charAt(j) == '0') {
					A |= (1 << (L - j - 1));
					ca++;
				} else if (s.charAt(j) == '1') {
					B |= (1 << (L - j - 1));
					cb++;
				} else {
					C |= (1 << (L - j - 1));
					cc++;
				}
			}

			if (ca <= cb && ca <= cc) {
				for (int m = A; m != 0; m = (m - 1) & A) {
					ans += (1 - 2 * ((btcnt[m]) & 1)) * sup[B | m];
				}
				ans += sup[B];
			} else if (cb <= ca && cb <= cc) {
				for (int m = B; m != 0; m = (m - 1) & B) {

					ans += (1 - 2 * ((btcnt[m]) & 1)) * sub[C | (B ^ m)];
				}
				ans += sub[C | B];

			} else {
				for (int m = C; m != 0; m = (m - 1) & C) { ans += S[m | B]; }

				ans += S[B];
			}
			sb.append(ans).append("\n");
			if ((i & ((1 << 17) - 1)) == 0) {  // sb can have a lot of memory
				System.out.println(sb.toString());
				sb = new StringBuilder();
			}
		}
		System.out.println(sb.toString());
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25