Submission #7875187


Source Code Expand

Copy
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Math.max;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	static int n;
	static long a[];
	static Map<Long, long[]> res;

	static void solve() throws Exception {
		n = scanInt();
		a = new long[2 * n];
		for (int i = 0; i < 2 * n; i++) {
			String l = scanString();
			long cur = 0;
			for (int j = 0; j < 2 * n; j++) {
				if (l.charAt(j) == '1') {
					cur |= 1L << j;
				}
			}
			a[i] = cur;
		}
		res = new HashMap<>();
		for (int i = 0; i < 2 * n; i++) {
			for (int j = i + 1; j < 2 * n; j++) {
				if ((a[i] & (1L << j)) != 0) {
					res.put((1L << i) | (1L << j), new long[] {1});
				}
			}
		}
		out.print(solve((1L << (2 * n)) - 1)[0]);
	}

	static long[] solve(long set) {
		long r[] = res.get(set);
		if (r == null) {
			int s = Long.bitCount(set), p = 0;
			r = new long[s - 1];
			for (int i = 2 * n - 1, i2 = -1, i3 = -1, j = s - 1; i >= 0; i--) {
				if ((set & (1L << i)) == 0) {
					continue;
				}
				if (j < s - 3) {
					if ((a[i] & (1L << i3)) != 0) {
						p += solve(set ^ (1L << i) ^ (1L << i3))[max(j - 2, 0)];
					}
					r[j] = p;
				}
				i3 = i2;
				i2 = i;
				--j;
			}
			res.put(set, r);
		}
		return r;
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

Submission Info

Submission Time
Task E - Pairing Points
User eatmore
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 2253 Byte
Status TLE
Exec Time 2110 ms
Memory 352028 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 3
AC × 10
TLE × 18
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt TLE 2110 ms 307536 KB
02.txt TLE 2110 ms 304360 KB
03.txt TLE 2110 ms 316576 KB
04.txt TLE 2110 ms 301236 KB
05.txt TLE 2110 ms 302256 KB
06.txt TLE 2110 ms 295188 KB
07.txt TLE 2110 ms 310532 KB
08.txt TLE 2110 ms 311576 KB
09.txt TLE 2110 ms 302056 KB
10.txt TLE 2110 ms 296796 KB
11.txt TLE 2110 ms 314456 KB
12.txt TLE 2110 ms 317164 KB
13.txt TLE 2110 ms 191172 KB
14.txt TLE 2110 ms 310176 KB
15.txt AC 72 ms 21972 KB
16.txt AC 69 ms 19284 KB
17.txt AC 72 ms 19284 KB
18.txt TLE 2110 ms 303584 KB
19.txt TLE 2110 ms 323620 KB
20.txt TLE 2110 ms 352028 KB
21.txt TLE 2110 ms 342552 KB
22.txt AC 69 ms 20436 KB
23.txt AC 69 ms 19028 KB
24.txt AC 67 ms 21204 KB
25.txt AC 70 ms 20564 KB
s1.txt AC 68 ms 21076 KB
s2.txt AC 69 ms 18516 KB
s3.txt AC 87 ms 19412 KB