結果
| 問題 | No.585 工夫のないパズル |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2019-06-15 03:22:34 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 6,372 bytes |
| コンパイル時間 | 1,049 ms |
| コンパイル使用メモリ | 124,724 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-22 01:45:27 |
| 合計ジャッジ時間 | 1,472 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,812 KB |
| testcase_01 | AC | 1 ms
6,940 KB |
| testcase_02 | AC | 1 ms
6,944 KB |
| testcase_03 | AC | 1 ms
6,940 KB |
| testcase_04 | AC | 1 ms
6,940 KB |
| testcase_05 | AC | 1 ms
6,940 KB |
| testcase_06 | AC | 1 ms
6,940 KB |
| testcase_07 | AC | 1 ms
6,940 KB |
| testcase_08 | AC | 1 ms
6,944 KB |
| testcase_09 | AC | 1 ms
6,944 KB |
| testcase_10 | AC | 1 ms
6,944 KB |
| testcase_11 | AC | 2 ms
6,940 KB |
| testcase_12 | AC | 1 ms
6,940 KB |
| testcase_13 | AC | 1 ms
6,940 KB |
| testcase_14 | AC | 1 ms
6,944 KB |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
Tuple!(int, int, int)[] ans;
int[][] rotR(int[][] a, int pos, int k) {
ans ~= tuple(0, pos, k);
auto b = new int[][](4, 4);
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
b[x][y] = a[x][y];
}
foreach (y; 0 .. 4) {
b[pos][(y + k) % 4] = a[pos][y];
}
return b;
}
int[][] rotC(int[][] a, int pos, int k) {
ans ~= tuple(1, pos, k);
auto b = new int[][](4, 4);
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
b[x][y] = a[x][y];
}
foreach (x; 0 .. 4) {
b[(x + k) % 4][pos] = a[x][pos];
}
return b;
}
string[] S;
void main() {
/*
// enum m = 4;
enum m = 8;
// foreach (p; 0 .. 24^^m) {
foreach (p; 0 .. 12^^m) {
auto dirs = new int[m];
auto poss = new int[m];
auto ks = new int[m];
// foreach (i; 0 .. m) {
// const key = p / 24^^i % 24;
// dirs[i] = key / 12;
// poss[i] = key % 12 / 3;
foreach (i; 0 .. m) {
const key = p / 12^^i % 12;
dirs[i] = key / 6;
poss[i] = key % 6 / 3;
ks[i] = 1 + key % 3;
}
auto a = new int[][](4, 4);
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
a[x][y] = x * 4 + y;
}
foreach (i; 0 .. m) {
a = (dirs[i] == 0) ? a.rotR(poss[i], ks[i]) : a.rotC(poss[i], ks[i]);
}
int cnt;
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
if (a[x][y] != x * 4 + y) {
++cnt;
}
}
if (1 <= cnt && cnt <= 2) {
writeln(dirs, " ", poss, " ", ks, ": ", cnt, " ", a);
stdout.flush;
}
}
//*/
/*
[1, 0, 1, 0, 1, 0, 1, 0] [1, 0, 1, 0, 1, 0, 1, 0] [3, 2, 1, 1, 3, 1, 1, 1]: 2 [[1, 0, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]]
*/
try {
for (; ; ) {
S = new string[4];
foreach (x; 0 .. 4) {
S[x] = readToken();
}
auto a = new int[][](4, 4);
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
a[x][y] = S[x][y] - 'A';
}
ans = [];
auto vis = new bool[][](4, 4);
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
if (x < 2 || y < 2) {
if (a[x][y] != x * 4 + y) {
debug {
// writeln(a);
}
if (x == 3 && y == 0 && a[3][1] == 3 * 4 + 0) {
debug {
writeln("3 0: !");
}
a = a.rotR(3, 3);
goto done;
}
foreach (p; 0 .. 4) foreach (q; 0 .. 4) foreach (r; 0 .. 4) foreach (s; 0 .. 4) {
if (p != r && q != s) {
if ((p == x && q == y) || (p == x && s == y) || (r == x && q == y)) {
if (!vis[p][q] && !vis[p][s] && !vis[r][q]) {
if (a[p][q] == x * 4 + y || a[p][s] == x * 4 + y || a[r][q] == x * 4 + y) {
debug {
writeln(x, " ", y, ": ", p, " ", q, " ", r, " ", s);
}
const kx = (p - r + 4) % 4;
const ky = (q - s + 4) % 4;
int[][] b;
b = a.rotR(p, ky).rotC(q, kx).rotR(p, 4 - ky).rotC(q, 4 - kx);
if (b[x][y] == x * 4 + y) {
a = b;
goto done;
}
ans = ans[0 .. $ - 4];
b = a.rotC(q, kx).rotR(p, ky).rotC(q, 4 - kx).rotR(p, 4 - ky);
if (b[x][y] == x * 4 + y) {
a = b;
goto done;
}
assert(false);
}
}
}
}
}
debug {
writeln(x, " ", y);
stdout.flush;
}
assert(false);
}
done:
vis[x][y] = true;
}
}
debug {
writeln(a);
}
if (a[3][3] == 2 * 4 + 2) {
for (; a[2][2] != 2 * 4 + 2; ) {
a = a.rotR(2, 1).rotC(3, 3).rotR(2, 3).rotC(3, 1);
}
} else {
for (; a[2][2] != 2 * 4 + 2; ) {
a = a.rotR(2, 3).rotC(2, 3).rotR(2, 1).rotC(2, 1);
}
}
debug {
writeln(a);
}
for (; a[2][3] != 2 * 4 + 3; ) {
a = a.rotR(3, 1).rotC(3, 1).rotR(3, 3).rotC(3, 3);
}
debug {
writeln(a);
}
// swap (3, 2) and (3, 3)
if (a[3][2] != 3 * 4 + 2) {
a = a.rotC(3, 3).rotR(3, 2)
.rotC(3, 1).rotR(3, 1)
.rotC(3, 3).rotR(3, 1)
.rotC(3, 1).rotR(3, 1);
debug {
writeln(a);
}
}
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
assert(a[x][y] == x * 4 + y);
}
/*
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
a[x][y] = S[x][y] - 'A';
}
foreach (line; ans) {
if (line[0] == 0) {
a = a.rotR(line[1], line[2]);
} else {
a = a.rotC(line[1], line[2]);
}
}
foreach (x; 0 .. 4) foreach (y; 0 .. 4) {
assert(a[x][y] == x * 4 + y);
}
*/
writeln(ans.length);
foreach (line; ans) {
writeln("RC"[line[0]], " ", line[1], " ", line[2]);
}
}
} catch (EOFException e) {
}
}