結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 Yu_212
|
| 提出日時 | 2022-06-12 17:18:34 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 767 ms / 2,000 ms |
| コード長 | 31,193 bytes |
| コンパイル時間 | 2,700 ms |
| 実行使用メモリ | 64,548 KB |
| スコア | 74,331 |
| 平均クエリ数 | 247.58 |
| 最終ジャッジ日時 | 2022-06-12 17:19:10 |
| 合計ジャッジ時間 | 35,729 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 148 ms
54,828 KB |
| testcase_01 | AC | 233 ms
58,744 KB |
| testcase_02 | AC | 178 ms
56,168 KB |
| testcase_03 | AC | 128 ms
52,252 KB |
| testcase_04 | AC | 167 ms
55,644 KB |
| testcase_05 | AC | 696 ms
63,188 KB |
| testcase_06 | AC | 232 ms
59,628 KB |
| testcase_07 | AC | 723 ms
63,292 KB |
| testcase_08 | AC | 177 ms
56,252 KB |
| testcase_09 | AC | 180 ms
56,076 KB |
| testcase_10 | AC | 160 ms
55,960 KB |
| testcase_11 | AC | 139 ms
53,012 KB |
| testcase_12 | AC | 150 ms
54,160 KB |
| testcase_13 | AC | 188 ms
56,784 KB |
| testcase_14 | AC | 159 ms
56,112 KB |
| testcase_15 | AC | 163 ms
55,744 KB |
| testcase_16 | AC | 154 ms
55,000 KB |
| testcase_17 | AC | 172 ms
56,480 KB |
| testcase_18 | AC | 258 ms
60,428 KB |
| testcase_19 | AC | 95 ms
51,192 KB |
| testcase_20 | AC | 139 ms
54,096 KB |
| testcase_21 | AC | 106 ms
51,512 KB |
| testcase_22 | AC | 163 ms
55,224 KB |
| testcase_23 | AC | 192 ms
57,680 KB |
| testcase_24 | AC | 256 ms
60,140 KB |
| testcase_25 | AC | 140 ms
53,580 KB |
| testcase_26 | AC | 676 ms
61,996 KB |
| testcase_27 | AC | 744 ms
64,548 KB |
| testcase_28 | AC | 102 ms
51,024 KB |
| testcase_29 | AC | 704 ms
63,800 KB |
| testcase_30 | AC | 138 ms
52,876 KB |
| testcase_31 | AC | 139 ms
53,256 KB |
| testcase_32 | AC | 186 ms
55,644 KB |
| testcase_33 | AC | 157 ms
54,984 KB |
| testcase_34 | AC | 185 ms
56,376 KB |
| testcase_35 | AC | 163 ms
56,068 KB |
| testcase_36 | AC | 178 ms
55,696 KB |
| testcase_37 | AC | 669 ms
63,252 KB |
| testcase_38 | AC | 767 ms
63,184 KB |
| testcase_39 | AC | 144 ms
54,088 KB |
| testcase_40 | AC | 157 ms
55,420 KB |
| testcase_41 | AC | 166 ms
56,084 KB |
| testcase_42 | AC | 177 ms
56,432 KB |
| testcase_43 | AC | 161 ms
55,676 KB |
| testcase_44 | AC | 117 ms
52,220 KB |
| testcase_45 | AC | 683 ms
63,220 KB |
| testcase_46 | AC | 669 ms
63,120 KB |
| testcase_47 | AC | 169 ms
55,960 KB |
| testcase_48 | AC | 141 ms
53,688 KB |
| testcase_49 | AC | 700 ms
64,200 KB |
| testcase_50 | AC | 148 ms
54,672 KB |
| testcase_51 | AC | 150 ms
54,404 KB |
| testcase_52 | AC | 172 ms
55,968 KB |
| testcase_53 | AC | 284 ms
60,424 KB |
| testcase_54 | AC | 154 ms
55,916 KB |
| testcase_55 | AC | 174 ms
56,332 KB |
| testcase_56 | AC | 168 ms
55,924 KB |
| testcase_57 | AC | 620 ms
63,256 KB |
| testcase_58 | AC | 169 ms
55,752 KB |
| testcase_59 | AC | 157 ms
55,192 KB |
| testcase_60 | AC | 136 ms
53,524 KB |
| testcase_61 | AC | 167 ms
55,968 KB |
| testcase_62 | AC | 199 ms
57,908 KB |
| testcase_63 | AC | 167 ms
56,328 KB |
| testcase_64 | AC | 395 ms
62,308 KB |
| testcase_65 | AC | 156 ms
56,260 KB |
| testcase_66 | AC | 137 ms
53,296 KB |
| testcase_67 | AC | 189 ms
56,568 KB |
| testcase_68 | AC | 716 ms
62,316 KB |
| testcase_69 | AC | 165 ms
55,656 KB |
| testcase_70 | AC | 103 ms
51,376 KB |
| testcase_71 | AC | 127 ms
51,844 KB |
| testcase_72 | AC | 154 ms
55,000 KB |
| testcase_73 | AC | 403 ms
61,164 KB |
| testcase_74 | AC | 624 ms
63,000 KB |
| testcase_75 | AC | 174 ms
56,544 KB |
| testcase_76 | AC | 204 ms
57,564 KB |
| testcase_77 | AC | 676 ms
63,392 KB |
| testcase_78 | AC | 151 ms
54,280 KB |
| testcase_79 | AC | 697 ms
63,892 KB |
| testcase_80 | AC | 138 ms
53,064 KB |
| testcase_81 | AC | 176 ms
55,468 KB |
| testcase_82 | AC | 148 ms
54,000 KB |
| testcase_83 | AC | 141 ms
53,248 KB |
| testcase_84 | AC | 169 ms
56,284 KB |
| testcase_85 | AC | 215 ms
58,408 KB |
| testcase_86 | AC | 131 ms
52,432 KB |
| testcase_87 | AC | 233 ms
58,800 KB |
| testcase_88 | AC | 755 ms
62,792 KB |
| testcase_89 | AC | 625 ms
62,184 KB |
| testcase_90 | AC | 169 ms
55,820 KB |
| testcase_91 | AC | 156 ms
54,816 KB |
| testcase_92 | AC | 246 ms
59,480 KB |
| testcase_93 | AC | 151 ms
54,448 KB |
| testcase_94 | AC | 665 ms
62,924 KB |
| testcase_95 | AC | 176 ms
55,576 KB |
| testcase_96 | AC | 162 ms
55,508 KB |
| testcase_97 | AC | 177 ms
56,464 KB |
| testcase_98 | AC | 736 ms
63,872 KB |
| testcase_99 | AC | 686 ms
62,144 KB |
ソースコード
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;
public class Main {
static In in = new In();
static Out out = new Out(false);
static final long inf = 0x1fffffffffffffffL;
static final int iinf = 0x3fffffff;
static final double eps = 1e-9;
static long mod = 998244353;
boolean isLocal = false;
double p;
int n = 20;
Pos[] instances = new Pos[n * n];
Pos[][] moved = new Pos[4][n * n];
String[] roads = new String[n * n];
double[][] walls = new double[4][n * n];
void solve() {
for (int i = 0; i < n * n; i++) {
instances[i] = new Pos(i % n, i / n, i);
}
for (int d = 0; d < 4; d++) {
for (int i = 0; i < n * n; i++) {
int nx = i % n + (d - 1) % 2;
int ny = i / n + (d - 2) % 2;
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
moved[d][i] = instances[ny * n + nx];
}
}
}
in.nextInt();
in.nextInt();
p = in.nextInt() / 100.0;
w = isLocal ? gen() : null;
roads[0] = "";
for (int i = 0; i < 4; i++) {
for (int j = 0; j < n * n; j++) {
if (pos(j).moved(i) == null) {
walls[i][j] = 1;
} else {
walls[i][j] = 0.5;
}
}
}
if (isLocal) {
debug(w);
}
for (int t = 0; t < 1000; t++) {
// BitBoard visited = BitBoard.zeros(n);
// visited.set(0, 0);
String ask = bfs(t);
// StringBuilder ask = dfs(pos(0, 0), 0, visited).reverse();
int ret = ask(ask.toString());
if (ret == -1) {
return;
}
}
if (isLocal) {
debug(w);
}
}
boolean[][] gen() {
boolean[][] w = new boolean[4][n * n];
int c = 0;
ThreadLocalRandom rand = ThreadLocalRandom.current();
int m = rand.nextInt(100, 200);
for (int i = 0; i < m; i++) {
if (rand.nextInt(2) == 0) {
int ii = rand.nextInt(0, 20);
int jj = rand.nextInt(0, 19);
w[2][ii * n + jj] = true;
w[0][ii * n + jj + 1] = true;
if (reachable(w) < n * n) {
w[2][ii * n + jj] = false;
w[0][ii * n + jj + 1] = false;
}
c++;
} else {
int ii = rand.nextInt(0, 19);
int jj = rand.nextInt(0, 20);
w[3][ii * n + jj] = true;
w[1][(ii + 1) * n + jj] = true;
if (reachable(w) < n * n) {
w[3][ii * n + jj] = false;
w[1][(ii + 1) * n + jj] = false;
}
c++;
}
}
return w;
}
int reachable(boolean[][] w) {
BitBoard bb = BitBoard.zeros(n);
Deque<Pos> deque = new ArrayDeque<>();
deque.addLast(pos(0));
bb.set(0, 0);
while (!deque.isEmpty()) {
Pos v = deque.remove();
for (int dir = 0; dir < 4; dir++) {
Pos nei = v.moved(dir);
if (nei == null || w[dir][v.z] || bb.get(nei.x, nei.y)) {
continue;
}
bb.set(nei.x, nei.y);
deque.addLast(nei);
}
}
return bb.countOne();
}
int virtual(boolean[][] w, String moves) {
Pos cur = pos(0, 0);
for (int i = 0; i < moves.length(); i++) {
int dir = "LURD".indexOf(moves.charAt(i));
if (ThreadLocalRandom.current().nextInt(100) <= p) {
return i;
}
if (cur.moved(dir) == null) {
throw new RuntimeException();
}
if (w[dir][cur.z]) {
return i;
}
cur = cur.moved(dir);
}
if (cur == pos(n - 1, n - 1)) {
return -1;
}
return moves.length();
}
String bfs(int turn) {
class State implements Comparable<State> {
final Pos pos;
final int dist;
final double prob;
State(Pos pos, int dist, double prob) {
this.pos = pos;
this.dist = dist;
this.prob = prob;
}
@Override
public int compareTo(State o) {
if (dist != o.dist) {
return Integer.compare(dist, o.dist);
} else if (prob != o.prob) {
return -Double.compare(prob, o.prob);
} else {
return Integer.compare(hashCode(), o.hashCode());
}
}
@Override
public String toString() {
return "State{" + "pos=" + pos + ", dist=" + dist + ", prob=" + prob + '}';
}
}
PriorityQueue<State> queue = new PriorityQueue<>();
int[] prev = new int[n * n];
State[] s = new State[n * n];
for (int i = 0; i < n * n; i++) {
s[i] = new State(pos(i), iinf, 0);
}
Arrays.fill(prev, -1);
s[0] = new State(pos(0), 0, 1);
queue.add(s[0]);
Pos best = null;
while (!queue.isEmpty()) {
State state = queue.remove();
Pos cur = state.pos;
if (s[cur.z].compareTo(state) > 0) {
continue;
}
if (best == null || s[best.z].dist < state.dist || s[best.z].dist == state.dist && s[best.z].prob < state.prob) {
best = cur;
}
for (int dir = 0; dir < 4; dir++) {
Pos nei = cur.moved(dir);
if (nei == null) {
continue;
}
if (walls[dir][cur.z] >= 0.9) {
continue;
}
double pp = state.prob * (1 - walls[dir][cur.z]);
State ss = new State(nei, state.dist + 1, pp);
if (s[nei.z].compareTo(ss) > 0) {
s[nei.z] = ss;
prev[nei.z] = dir;
queue.add(ss);
}
}
}
if (isLocal) {
out.debug(s[n * n - 1]);
StringBuilder bb = new StringBuilder();
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// bb.append(String.format("%1.1f", walls[2][i * n + j])).append("|").append(String.format("%1.1f", walls[3][i * n + j])).append(", ");
// }
// bb.append('\n');
// }
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// bb.append(s[i * n + j].dist).append(", ");
// }
// bb.append('\n');
// }
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// bb.append(String.format("%2.3f", s[i * n + j].prob)).append(", ");
// }
// bb.append('\n');
// }
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// bb.append(prev[i * n + j]).append(", ");
// }
// bb.append('\n');
// }
// out.debug(bb);
}
if (turn >= 10) {
best = pos(n * n - 1);
}
StringBuilder ret = new StringBuilder();
while (best.z != 0) {
ret.append("LURD".charAt(prev[best.z]));
best = best.moved((prev[best.z] + 2) % 4);
}
return ret.reverse().toString();
}
// StringBuilder dfs(Pos cur, int depth, BitBoard visited) {
// List<Integer> cand = new ArrayList<>();
// for (int dir = 0; dir < 4; dir++) {
// Pos nei = cur.moved(dir);
// if (nei == null || visited.get(nei.x, nei.y) || walls[dir][cur.z] > 0.9) {
// continue;
// }
// cand.add(dir);
// }
// if (cand.isEmpty()) {
// return new StringBuilder();
// }
// cand.sort(Comparator.comparingDouble(i -> walls[i][cur.z]));
// int dir = cand.get(0);
// Pos nei = cur.moved(dir);
// visited.set(nei.x, nei.y);
// String ret = bfs();
// visited.clear(nei.x, nei.y);
// ret.append("LURD".charAt(dir));
// double prob = (1 - walls[dir][cur.z]) * ret.length();
// return ret;
// }
void debug(boolean[][] w) {
char[][] c = new char[n][n * 2 - 1];
for (int i = 0; i < n; i++) {
Arrays.fill(c[i], ' ');
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (w[2][i * n + j]) {
c[i][j * 2 + 1] = '|';
}
if (w[3][i * n + j]) {
c[i][j * 2] = '_';
}
}
}
for (int i = 0; i < n; i++) {
out.debug(String.valueOf(c[i]));
}
}
boolean[][] w;
int ask(String moves) {
Pos cur = pos(0, 0);
out.println(moves);
out.flush();
int k = isLocal ? virtual(w, moves) : in.nextInt();
out.debug(k);
if (k == -1) {
return -1;
}
int len = moves.length();
for (int i = 0; i <= k && i < len; i++) {
int dir = "LURD".indexOf(moves.charAt(i));
if (i == k) {
out.debug(cur, dir, walls[dir][cur.z], walls[dir][cur.z] / (walls[dir][cur.z] + p));
walls[dir][cur.z] = walls[dir][cur.z] / (walls[dir][cur.z] + p);
} else {
String sub = moves.substring(0, i);
if (roads[cur.z] == null || roads[cur.z].length() > sub.length()) {
roads[cur.z] = sub;
}
walls[dir][cur.z] = 0;
}
cur = cur.moved(dir);
}
return k;
}
Pos pos(int x, int y) {
return instances[y * n + x];
}
Pos pos(int z) {
return instances[z];
}
class Pos implements Comparable<Pos> {
final int x, y, z;
private Pos(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
Pos moved(int d) {
return moved[d][z];
}
int dist(Pos o) {
return Math.abs(x - o.x) + Math.abs(y - o.y);
}
int euclid(Pos o) {
return Math.abs(x - o.x) + Math.abs(y - o.y);
}
Pos[] neighbors() {
Pos[] p = new Pos[4];
int i = 0;
if ((p[i++] = moved(0)) == null) i--;
if ((p[i++] = moved(1)) == null) i--;
if ((p[i++] = moved(2)) == null) i--;
if ((p[i++] = moved(3)) == null) i--;
return Arrays.copyOf(p, i);
}
@Override
public int compareTo(Pos o) {
return Integer.compare(z, o.z);
}
@Override
public boolean equals(Object o) {
return o instanceof Pos && z == ((Pos)o).z;
}
@Override
public int hashCode() {
return z;
}
@Override
public String toString() {
return String.format("(%d, %d)", x, y);
}
}
static abstract class BitBoard {
private static final long[] MASKS = {0, 0x1L, 0x3L, 0x7L, 0xFL, 0x1FL, 0x3FL, 0x7FL, 0xFFL, 0x1FFL, 0x3FFL, 0x7FFL, 0xFFFL, 0x1FFFL, 0x3FFFL, 0x7FFFL, 0xFFFFL, 0x1FFFFL, 0x3FFFFL, 0x7FFFFL, 0xFFFFFL, 0x1FFFFFL, 0x3FFFFFL, 0x7FFFFFL, 0xFFFFFFL, 0x1FFFFFFL, 0x3FFFFFFL, 0x7FFFFFFL, 0xFFFFFFFL, 0x1FFFFFFFL, 0x3FFFFFFFL, 0x7FFFFFFFL, 0xFFFFFFFFL, 0x1FFFFFFFFL, 0x3FFFFFFFFL, 0x7FFFFFFFFL, 0xFFFFFFFFFL, 0x1FFFFFFFFFL, 0x3FFFFFFFFFL, 0x7FFFFFFFFFL, 0xFFFFFFFFFFL, 0x1FFFFFFFFFFL, 0x3FFFFFFFFFFL, 0x7FFFFFFFFFFL, 0xFFFFFFFFFFFL, 0x1FFFFFFFFFFFL, 0x3FFFFFFFFFFFL, 0x7FFFFFFFFFFFL, 0xFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFL, 0x3FFFFFFFFFFFFL, 0x7FFFFFFFFFFFFL, 0xFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFFFL};
private static class BitBoard8 extends BitBoard { // [][][][][][][][] x1
private final static long[] ONES = {0, 0x1L, 0x101L, 0x10101L, 0x1010101L, 0x101010101L, 0x10101010101L, 0x1010101010101L, 0x101010101010101L};
private BitBoard8(int size) {
super(size, new long[1]);
}
private BitBoard8(int size, long[] board) {
super(size, board);
}
public BitBoard copy() {
return new BitBoard8(size, board);
}
protected int x(int x, int y) {
return y << 3 | x;
}
protected int y(int x, int y) {
return 0;
}
public long line(int y) {
return board[0] >>> (y << 3) & 0xFF;
}
public int countOne() {
return Long.bitCount(board[0]);
}
public void fillOnes() {
board[0] = ONES[size] * MASKS[size];
}
public void spread() {
board[0] |= spread(board[0], 8, ONES[size]) & MASKS[size * 8];
}
private static BitBoard compress(long[] lines) {
long board = 0;
for (long line : lines) {
board = board << 8 | line;
}
return new BitBoard8(lines.length, new long[] {board});
}
}
private static class BitBoard16 extends BitBoard { // [ ][ ][ ][ ] x4
private final static long[] ONES = {0x1000100010001L, 0x1L, 0x10001L, 0x100010001L};
private BitBoard16(int size) {
super(size, new long[(size + 3) >> 2]);
}
private BitBoard16(int size, long[] board) {
super(size, board);
}
public BitBoard copy() {
return new BitBoard16(size, board);
}
protected int x(int x, int y) {
return (y & 3) << 4 | x;
}
protected int y(int x, int y) {
return y >> 2;
}
public long line(int y) {
return board[y >> 2] >>> ((y & 3) << 4) & 0xFFFF;
}
public int countOne() {
if (board.length == 3) {
return Long.bitCount(board[0]) + Long.bitCount(board[1]) + Long.bitCount(board[2]);
} else {
return Long.bitCount(board[0]) + Long.bitCount(board[1]) + Long.bitCount(board[2]) + Long.bitCount(board[3]);
}
}
public void fillOnes() {
board[0] = ONES[0] * MASKS[size];
board[1] = ONES[0] * MASKS[size];
if (board.length == 3) {
board[2] = ONES[size & 3] * MASKS[size];
} else {
board[2] = ONES[0] * MASKS[size];
board[3] = ONES[size & 3] * MASKS[size];
}
}
public void spread() {
long old0 = board[0];
long old1 = board[1];
long old2 = board[2];
board[0] |= spread(old0, 16, ONES[0]) | old1 << 48;
board[1] |= spread(old1, 16, ONES[0]) | old2 << 48 | old0 >>> 48;
if (board.length == 3) {
board[2] |= spread(old2, 16, ONES[0]) & MASKS[(size - 8) * 16] | old1 >>> 48;
} else {
long old3 = board[3];
board[2] |= spread(old2, 16, ONES[0]) | old3 << 48 | old1 >>> 48;
board[3] |= spread(old3, 16, ONES[0]) & MASKS[(size - 12) * 16] | old2 >>> 48;
}
}
private static BitBoard compress(long[] lines) {
long[] board = new long[lines.length >> 2];
for (int i = 0; i < lines.length; i++) {
board[i >> 2] = board[i >> 2] << 16 | lines[i];
}
return new BitBoard16(lines.length, board);
}
}
private static class BitBoard32 extends BitBoard { // [ ][ ] x16
private BitBoard32(int size) {
super(size, new long[(size + 1) >> 1]);
}
private BitBoard32(int size, long[] board) {
super(size, board);
}
public BitBoard copy() {
return new BitBoard32(size, board);
}
protected int x(int x, int y) {
return (y & 1) << 5 | x;
}
protected int y(int x, int y) {
return y >> 1;
}
public long line(int y) {
return board[y >> 1] >>> ((y & 1) << 5) & 0xFFFFFFFFL;
}
public void fillOnes() {
Arrays.fill(board, MASKS[size] << 16 | MASKS[size]);
if ((size & 1) == 1) {
board[board.length - 1] = MASKS[size];
}
}
public void spread() {
long old = 0;
for (int i = 0; i < board.length; i++) {
if (i > 0) {
board[i - 1] |= board[i] << 32;
}
long old2 = board[i];
board[i] |= spread(board[i], 32, 0x100000001L) | old >>> 32;
old = old2;
}
if ((size & 1) == 1) {
board[board.length - 1] &= 0xFFFFFFFFL;
}
}
private static BitBoard compress(long[] lines) {
long[] board = new long[lines.length >> 2];
for (int i = 0; i < lines.length; i++) {
board[i >> 2] = board[i >> 2] << 16 | lines[i];
}
return new BitBoard32(lines.length, board);
}
}
private static class BitBoard64 extends BitBoard { // [ ] x64
private BitBoard64(int size) {
super(size, new long[size]);
}
private BitBoard64(int size, long[] board) {
super(size, board);
}
public BitBoard copy() {
return new BitBoard64(size, board);
}
protected int x(int x, int y) {
return x;
}
protected int y(int x, int y) {
return y;
}
public long line(int y) {
return board[y];
}
public void fillOnes() {
Arrays.fill(board, MASKS[size]);
}
public void spread() {
long old = 0;
for (int i = 0; i < board.length; i++) {
if (i > 0) {
board[i - 1] |= board[i];
}
long old2 = board[i];
board[i] |= old | board[i] >>> 1 | board[i] << 1 & MASKS[size];
old = old2;
}
}
private static BitBoard compress(long[] lines) {
return new BitBoard64(lines.length, lines);
}
}
protected final long[] board;
protected final byte size;
private BitBoard(int size, long[] board) {
this.size = (byte)size;
this.board = board;
}
public static BitBoard of(long[] lines) {
int size = lines.length;
if (size <= 8) {
return BitBoard8.compress(lines);
} else if (size <= 16) {
return BitBoard16.compress(lines);
} else if (size <= 32) {
return BitBoard32.compress(lines);
} else if (size <= 64) {
return BitBoard64.compress(lines);
}
throw new IllegalArgumentException();
}
public static BitBoard zeros(int size) {
if (0 <= size) {
if (size <= 8) {
return new BitBoard8(size);
} else if (size <= 16) {
return new BitBoard16(size);
} else if (size <= 32) {
return new BitBoard32(size);
} else if (size <= 64) {
return new BitBoard64(size);
}
}
throw new IllegalArgumentException();
}
public static BitBoard ones(int size) {
BitBoard board = zeros(size);
board.fillOnes();
return board;
}
protected long spread(long a, int b, long ones) {
long shiftLeft = (a & ~ones) >>> 1;
long shiftRight = (a & ~(ones << size - 1)) << 1;
return shiftLeft | shiftRight | a << b | a >>> b;
}
protected abstract int x(int x, int y);
protected abstract int y(int x, int y);
public abstract BitBoard copy();
public abstract long line(int y);
public abstract void fillOnes();
public abstract void spread();
public BitBoard subboard(int sx, int sy, int size) {
long[] lines = new long[size];
for (int i = 0; i < size; i++) {
lines[i] = line(sy + i) >> sx & MASKS[size];
}
return BitBoard.of(lines);
}
public void set(int x, int y) {
Objects.checkIndex(x, size);
Objects.checkIndex(y, size);
board[y(x, y)] |= 1L << x(x, y);
}
public void set(int x, int y, boolean value) {
if (value) {
set(x, y);
} else {
clear(x, y);
}
}
public void flip(int x, int y) {
Objects.checkIndex(x, size);
Objects.checkIndex(y, size);
board[y(x, y)] ^= 1L << x(x, y);
}
public void clear(int x, int y) {
Objects.checkIndex(x, size);
Objects.checkIndex(y, size);
board[y(x, y)] &= ~(1L << x(x, y));
}
public boolean get(int x, int y) {
Objects.checkIndex(x, size);
Objects.checkIndex(y, size);
return (line(y) >>> x & 1) == 1;
}
public void and(BitBoard o) {
for (int i = 0; i < board.length; i++) {
board[i] &= o.board[i];
}
}
public void or(BitBoard o) {
for (int i = 0; i < board.length; i++) {
board[i] |= o.board[i];
}
}
public void xor(BitBoard o) {
for (int i = 0; i < board.length; i++) {
board[i] ^= o.board[i];
}
}
public void andNot(BitBoard o) {
for (int i = 0; i < board.length; i++) {
board[i] &= ~o.board[i];
}
}
public int size() {
return size;
}
public int countOne() {
int count = 0;
for (long bits : board) {
count += Long.bitCount(bits);
}
return count;
}
public int countZero() {
return size * size - countOne();
}
@Override
public int hashCode() {
long h = 1234;
for (int i = 0; i < board.length; i++) {
h ^= board[i] * (i + 1);
}
return (int)(h >> 32 ^ h);
}
@Override
public boolean equals(Object o) {
return this == o || o instanceof BitBoard && Arrays.equals(board, ((BitBoard)o).board);
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
builder.append(get(j, i) ? 'o' : '.');
}
if (i + 1 < size) {
builder.append('\n');
}
}
return builder.toString();
}
}
public static void main(String... args) {
try {
new Main().solve();
out.flush();
} catch (Exception e) {
}
}
}
class In {
private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
private StringTokenizer tokenizer;
String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
} catch (IOException ignored) {
}
return tokenizer.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
char[] nextCharArray() {
return next().toCharArray();
}
String[] nextStringArray(int n) {
String[] s = new String[n];
for (int i = 0; i < n; i++) {
s[i] = next();
}
return s;
}
char[][] nextCharGrid(int n, int m) {
char[][] a = new char[n][m];
for (int i = 0; i < n; i++) {
a[i] = next().toCharArray();
}
return a;
}
int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
int[] nextIntArray(int n, IntUnaryOperator op) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = op.applyAsInt(nextInt());
}
return a;
}
int[][] nextIntMatrix(int h, int w) {
int[][] a = new int[h][w];
for (int i = 0; i < h; i++) {
a[i] = nextIntArray(w);
}
return a;
}
long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nextLong();
}
return a;
}
long[] nextLongArray(int n, LongUnaryOperator op) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = op.applyAsLong(nextLong());
}
return a;
}
long[][] nextLongMatrix(int h, int w) {
long[][] a = new long[h][w];
for (int i = 0; i < h; i++) {
a[i] = nextLongArray(w);
}
return a;
}
List<List<Integer>> nextEdges(int n, int m, boolean directed) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int u = nextInt() - 1;
int v = nextInt() - 1;
res.get(u).add(v);
if (!directed) {
res.get(v).add(u);
}
}
return res;
}
}
class Out {
private final PrintWriter out = new PrintWriter(System.out);
private final PrintWriter err = new PrintWriter(System.err);
boolean autoFlush = false;
boolean enableDebug;
Out(boolean enableDebug) {
this.enableDebug = enableDebug;
}
void println(Object... args) {
if (args == null || args.getClass() != Object[].class) {
args = new Object[] {args};
}
out.println(Arrays.stream(args).map(obj -> {
Class<?> clazz = obj == null ? null : obj.getClass();
return clazz == Double.class ? String.format("%.10f", obj) :
clazz == byte[].class ? Arrays.toString((byte[])obj) :
clazz == short[].class ? Arrays.toString((short[])obj) :
clazz == int[].class ? Arrays.toString((int[])obj) :
clazz == long[].class ? Arrays.toString((long[])obj) :
clazz == char[].class ? Arrays.toString((char[])obj) :
clazz == float[].class ? Arrays.toString((float[])obj) :
clazz == double[].class ? Arrays.toString((double[])obj) :
clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
String.valueOf(obj);
}).collect(Collectors.joining(" ")));
if (autoFlush) {
out.flush();
}
}
void debug(Object... args) {
if (!enableDebug) {
return;
}
if (args == null || args.getClass() != Object[].class) {
args = new Object[] {args};
}
err.println(Arrays.stream(args).map(obj -> {
Class<?> clazz = obj == null ? null : obj.getClass();
return clazz == Double.class ? String.format("%.10f", obj) :
clazz == byte[].class ? Arrays.toString((byte[])obj) :
clazz == short[].class ? Arrays.toString((short[])obj) :
clazz == int[].class ? Arrays.toString((int[])obj) :
clazz == long[].class ? Arrays.toString((long[])obj) :
clazz == char[].class ? Arrays.toString((char[])obj) :
clazz == float[].class ? Arrays.toString((float[])obj) :
clazz == double[].class ? Arrays.toString((double[])obj) :
clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
String.valueOf(obj);
}).collect(Collectors.joining(" ")));
err.flush();
}
void println(char[] s) {
out.println(String.valueOf(s));
if (autoFlush) {
out.flush();
}
}
void println(int[] a) {
StringJoiner joiner = new StringJoiner(" ");
for (int i : a) {
joiner.add(Integer.toString(i));
}
out.println(joiner);
if (autoFlush) {
out.flush();
}
}
void println(long[] a) {
StringJoiner joiner = new StringJoiner(" ");
for (long i : a) {
joiner.add(Long.toString(i));
}
out.println(joiner);
if (autoFlush) {
out.flush();
}
}
void flush() {
err.flush();
out.flush();
}
}