結果
問題 | No.1056 2D Lamps |
ユーザー | uwi |
提出日時 | 2020-05-22 20:44:22 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,294 ms / 3,000 ms |
コード長 | 7,416 bytes |
コンパイル時間 | 4,331 ms |
コンパイル使用メモリ | 88,164 KB |
実行使用メモリ | 116,684 KB |
最終ジャッジ日時 | 2024-10-05 12:41:54 |
合計ジャッジ時間 | 18,174 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
37,040 KB |
testcase_01 | AC | 47 ms
37,048 KB |
testcase_02 | AC | 47 ms
37,172 KB |
testcase_03 | AC | 1,273 ms
116,300 KB |
testcase_04 | AC | 1,294 ms
116,432 KB |
testcase_05 | AC | 1,275 ms
116,380 KB |
testcase_06 | AC | 1,251 ms
116,572 KB |
testcase_07 | AC | 1,254 ms
116,320 KB |
testcase_08 | AC | 1,253 ms
116,648 KB |
testcase_09 | AC | 1,098 ms
116,440 KB |
testcase_10 | AC | 1,213 ms
116,684 KB |
testcase_11 | AC | 1,098 ms
116,472 KB |
testcase_12 | AC | 1,087 ms
116,608 KB |
testcase_13 | AC | 49 ms
36,904 KB |
testcase_14 | AC | 91 ms
39,920 KB |
testcase_15 | AC | 92 ms
39,408 KB |
testcase_16 | AC | 94 ms
39,160 KB |
ソースコード
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;int R = rank(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-1;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^62long mid = al * bh + bl * ah; // < 2^62long 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 Eliminationfor(int i = 0;i < n;i++){// select pivotboolean pivotFound = false;out:for(int pi = i;pi < n;pi++){for(int pj = i;pj < m;pj++){if(M[pi][pj]){// pivot found// swap columnsfor(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 rowsfor(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)); }}