#482126 (Java21) No.1056 2D Lamps

提出ソース

結果

問題	No.1056 2D Lamps
ユーザー	uwi
提出日時	2020-05-15 22:14:06
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	7,432 bytes
コンパイル時間	3,941 ms
コンパイル使用メモリ	81,504 KB
実行使用メモリ	38,320 KB
最終ジャッジ日時	2024-09-19 11:03:12
合計ジャッジ時間	9,623 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	TLE	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

package contest200515;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class E {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), m = ni();
		boolean[][] M = new boolean[n+n+(2*n-1)+(2*n-1)][n*n];
		int p = 0;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				M[p][i*n+j] = true;
			}
			p++;
			for(int j = 0;j < n;j++){
				M[p][j*n+i] = true;
			}
			p++;
		}
		for(int i = 0;i <= 2*(n-1);i++){
			for(int j = 0;j < n;j++){
				int k = i-j;
				if(k >= 0 && k < n){
					M[p][j*n+k] = true;
				}
			}
			p++;
		}
		for(int i = -(n-1);i <= n-1;i++){
			for(int j = 0;j < n;j++){
				int k = i+j;
				if(k >= 0 && k < n){
					M[p][j*n+k] = true;
				}
			}
			p++;
		}
		assert p == M.length;
		tf(M);
		int R = rank(M);
		tf(M);
		long[][] H = new long[R][(n*n>>>6)+1];
		int[] iord = new int[n*n];
		for(int i = 0;i < n*n;i++){
			iord[oord[i]] = i;
		}
		for(int i = 0;i < R;i++){
			for(int j = 0;j < n*n;j++){
				if(M[i][j])H[i][j>>>6] ^= 1L<<j;
			}
		}
		long[] hs = new long[m];
		for(int i = 0;i < m;i++){
			RollingHash61 rh = new RollingHash61(31, (n*n>>>6)+1);
			char[][] map = nm(n,n);
			long[] v = new long[(n*n>>>6)+1];
			for(int j = 0;j < n;j++){
				for(int k = 0;k < n;k++){
					if(map[j][k] == '#'){
						v[iord[j*n+k]>>>6] |= 1L<<iord[j*n+k];
					}
				}
			}
			for(int j = 0;j < R;j++){
				if(v[j>>>6]<<~j<0){
					for(int k = 0;k < (n*n>>>6)+1;k++){
						v[k] ^= H[j][k];
					}
				}
			}
			long hash = 0;
			for(int k = 0;k < (n*n>>>6)+1;k++){
				rh.add(v[k]);
//				hash = hash * 1000000009 + v[k];
			}
			hs[i] = rh.h(0, (n*n>>>6)+1);
		}
		for(int i = 0;i < m;i++){
			for(int j = i+1;j < m;j++){
				out.print(hs[i] == hs[j] ? 1 : 0);
			}
			out.println();
		}
	}
	
	
	public static class RollingHash61
	{
		static final long mod = (1L<<61)-1;
		public long M;
		public long[] pows;
		public long[] hs;
		public int hp;
		
		public RollingHash61(long M, int n) {
			assert M > 0;
			assert n > 0;
			this.M = M;
			this.pows = makePows(M, n);
			this.hs = new long[n+1];
			this.hp = 0;
		}
		
		public static long mul(long a, long b)
		{
			long al = a&(1L<<31)-1, ah = a>>>31;
			long bl = b&(1L<<31)-1, bh = b>>>31;
			long low = al * bl; // <2^62
			long mid = al * bh + bl * ah; // < 2^62
			long high = ah * bh + (mid>>>31); // < 2^60 + 2^31 < 2^61
			// high*2^62 = high*2 (mod 2^61-1)
			long ret = mod(mod(2*high + low) + ((mid&(1L<<31)-1)<<31));
			return ret;
		}
		
		public static long mod(long a)
		{
			while(a >= mod)a -= mod;
			while(a < 0)a += mod;
			return a;
		}
		
		private static long[] makePows(long M, int n)
		{
			long[] ret = new long[n+1];
			ret[0] = 1;
			for(int i = 1;i <= n;i++)ret[i] = mul(ret[i-1], M);
			return ret;
		}
		
		public void add(long x)
		{
			hs[hp+1] = mul(hs[hp], M) + x;
			if(hs[hp+1] >= mod)hs[hp+1] -= mod;
			hp++;
		}
		
		public long h(int l, int r)
		{
			assert l <= r;
			return mod(hs[r] - mul(hs[l], pows[r-l]));
		}
	}

	public static boolean[][] trans(boolean[][] a)
	{
		if(a.length == 0)return new boolean[0][0];
		int n = a.length, m = a[0].length;
		boolean[][] ret = new boolean[m][n];
		for(int i = 0;i < m;i++){
			for(int j = 0;j < n;j++){
				ret[i][j] = a[j][i];
			}
		}
		return ret;
	}
	
	public static void tf(boolean[]... b)
	{
		for(boolean[] r : b) {
			for(boolean x : r)System.out.print(x?'#':'.');
			System.out.println();
		}
		System.out.println();
	}

	static int[] oord;
	
	public static int rank(boolean[][] M)
	{
		int n = M.length, m = M[0].length;
		int[] ord = new int[m];
		for(int i = 0;i < m;i++){
			ord[i] = i;
		}
		oord = ord;
		
		// Forward Elimination
		for(int i = 0;i < n;i++){
			// select pivot
			boolean pivotFound = false;
			out:
			for(int pi = i;pi < n;pi++){
				for(int pj = i;pj < m;pj++){
					if(M[pi][pj]){
						// pivot found
						// swap columns
						for(int k = 0;k < n;k++){
							boolean u = M[k][pj]; M[k][pj] = M[k][i]; M[k][i] = u;
						}
						int d = ord[pj]; ord[pj] = ord[i]; ord[i] = d;
						if(pi != i){
							// swap rows
							for(int k = 0;k < m;k++){
								boolean u = M[pi][k]; M[pi][k] = M[i][k]; M[i][k] = u;
							}
						}
						pivotFound = true;
						break out;
					}
				}
			}
			if(!pivotFound)return i;
			
			for(int j = i+1;j < n;j++){
				if(M[j][i]){
					for(int k = i;k < m;k++){
						M[j][k] ^= M[i][k];
					}
				}
			}
		}
		for(int j = n-1;j >= 0;j--){
			for(int i = j-1;i >= 0;i--){
				if(M[i][j]){
					for(int k = j;k < m;k++){
						M[i][k] ^= M[j][k];
					}
				}
			}
		}
		
		return n;
	}

	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new E().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

yukicoder

結果

テストケース

ソースコード