結果
| 問題 |
No.3338 Whole Reverse Contradiction
|
| コンテスト | |
| ユーザー |
 kencho
|
| 提出日時 | 2025-10-15 09:24:22 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 361 ms / 2,000 ms |
| コード長 | 18,781 bytes |
| コンパイル時間 | 2,882 ms |
| コンパイル使用メモリ | 89,160 KB |
| 実行使用メモリ | 57,796 KB |
| 最終ジャッジ日時 | 2025-11-07 20:36:08 |
| 合計ジャッジ時間 | 21,808 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 66 |
ソースコード
import java.util.ArrayDeque;
import java.util.ArrayList;
public class Main {
public static final int MOD998 = 998244353;
public static final int MOD100 = 1000000007;
static ArrayList<Integer> ope = new ArrayList<>();
public static void main(String[] args) throws Exception {
ContestScanner sc = new ContestScanner();
ContestPrinter cp = new ContestPrinter();
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
solve(sc, cp);
}
cp.close();
}
static void solve(ContestScanner sc, ContestPrinter cp) {
ope = new ArrayList<>();
int N = sc.nextInt();
int[][] A = sc.nextIntMatrix(N, N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
A[i][j]--;
}
}
if (N % 2 == 1) {
if (A[N / 2][0] != N / 2 * N) {
reverseRow(A, N / 2);
} else {
reverseRow(A, 0);
}
if (A[0][N / 2] != N / 2) {
reverseCol(A, N / 2);
} else {
reverseCol(A, 0);
}
for (int i = 0; i < N; i++) {
if (A[N / 2][i] != N / 2 * N + i) {
cp.println(-1);
return;
}
if (A[i][N / 2] != i * N + N / 2) {
cp.println(-1);
return;
}
}
}
ArrayDeque<Integer> revrow = new ArrayDeque<>();
for (int i = 0; i < N / 2; i++) {
int[] mem = new int[4];
mem[0] = A[i][0];
mem[1] = A[i][N - 1];
mem[2] = A[N - i - 1][0];
mem[3] = A[N - i - 1][N - 1];
int swap = 0;
for (int p = 2; p >= 0; p--) {
for (int q = p; q < 3; q++) {
if (mem[q] > mem[q + 1]) {
int tem = mem[q];
mem[q] = mem[q + 1];
mem[q + 1] = tem;
swap++;
}
}
}
if (swap % 2 == 1) {
revrow.add(i);
}
}
ArrayDeque<Integer> revcol = new ArrayDeque<>();
for (int i = 1; i < N / 2; i++) {
int[] mem = new int[4];
mem[0] = A[0][i];
mem[1] = A[0][N - i - 1];
mem[2] = A[N - 1][i];
mem[3] = A[N - 1][N - i - 1];
int swap = 0;
for (int p = 2; p >= 0; p--) {
for (int q = p; q < 3; q++) {
if (mem[q] > mem[q + 1]) {
int tem = mem[q];
mem[q] = mem[q + 1];
mem[q + 1] = tem;
swap++;
}
}
}
if ((!revrow.isEmpty() && revrow.peek() == 0) == (swap % 2 == 0)) {
revcol.add(i);
}
}
boolean rv = false;
while (!revrow.isEmpty() || !revcol.isEmpty()) {
if (revrow.isEmpty()) {
reverseRow(A, 0);
rv = !rv;
reverseCol(A, revcol.poll());
if (revcol.isEmpty() && rv) {
reverseRow(A, 0);
rv = !rv;
}
} else if (revcol.isEmpty()) {
reverseRow(A, revrow.poll());
if (!revrow.isEmpty() || rv) {
reverseCol(A, 0);
rv = !rv;
}
} else {
reverseRow(A, revrow.poll());
reverseCol(A, revcol.poll());
}
}
if (ope.size() % 2 == 1) {
int[][] copy = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int v = A[i][j];
int r = v / N;
int c = v % N;
copy[j][i] = c * N + r;
}
}
A = copy;
}
for (int i = 0; i < N / 2; i++) {
for (int j = 0; j < N / 2; j++) {
int[] mem = new int[4];
int[] memcopy = new int[4];
mem[0] = A[i][j];
mem[1] = A[i][N - j - 1];
mem[2] = A[N - i - 1][j];
mem[3] = A[N - i - 1][N - j - 1];
System.arraycopy(mem, 0, memcopy, 0, 4);
int swap = 0;
for (int p = 2; p >= 0; p--) {
for (int q = p; q < 3; q++) {
if (mem[q] > mem[q + 1]) {
int tem = mem[q];
mem[q] = mem[q + 1];
mem[q + 1] = tem;
swap++;
}
}
}
if (swap % 2 == 1 || mem[0] != i * N + j || mem[1] != i * N + (N - j - 1)
|| mem[2] != (N - i - 1) * N + j || mem[3] != (N - i - 1) * N + (N - j - 1)) {
cp.println(-1);
return;
}
for (int p = 0; p < 4; p++) {
for (int q = 0; q < 4; q++) {
if (memcopy[q] == mem[p]) {
memcopy[q] = p;
break;
}
}
}
int[][] pats = new int[][] { { i, j, i, j }, { i, N - j - 1, i, N - j - 1 },
{ N - i - 1, j, N - i - 1, j }, { N - i - 1, N - j - 1, N - i - 1, N - j - 1 } };
while (memcopy[0] != 0 || memcopy[1] != 1 || memcopy[2] != 2 || memcopy[3] != 3) {
int op = -1;
if (memcopy[0] == 0) {
op = 3;
} else if (memcopy[0] == 1) {
op = 1;
} else if (memcopy[0] == 2) {
op = 0;
} else {
op = 2;
}
for (int p = 0; p < 4; p++) {
ope.add(pats[op][p] + 1);
}
if (op == 0) {
int tem = memcopy[0];
memcopy[0] = memcopy[1];
memcopy[1] = memcopy[2];
memcopy[2] = tem;
} else if (op == 1) {
int tem = memcopy[1];
memcopy[1] = memcopy[0];
memcopy[0] = memcopy[3];
memcopy[3] = tem;
} else if (op == 2) {
int tem = memcopy[2];
memcopy[2] = memcopy[3];
memcopy[3] = memcopy[0];
memcopy[0] = tem;
} else {
int tem = memcopy[3];
memcopy[3] = memcopy[2];
memcopy[2] = memcopy[1];
memcopy[1] = tem;
}
}
}
}
cp.println(ope.size());
for (int i = 0; i < ope.size(); i++) {
cp.print(ope.get(i) + (i == ope.size() - 1 ? "\n" : " "));
}
}
static void reverseRow(int[][] mat, int row) {
ope.add(row + 1);
int i = 0;
int j = mat[row].length - 1;
while (i < j) {
int tem = mat[row][i];
mat[row][i] = mat[row][j];
mat[row][j] = tem;
i++;
j--;
}
}
static void reverseCol(int[][] mat, int col) {
ope.add(col + 1);
int i = 0;
int j = mat.length - 1;
while (i < j) {
int tem = mat[i][col];
mat[i][col] = mat[j][col];
mat[j][col] = tem;
i++;
j--;
}
}
static class ContestScanner {
private final java.io.InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private static final long LONG_MAX_TENTHS = 922337203685477580L;
private static final int LONG_MAX_LAST_DIGIT = 7;
private static final int LONG_MIN_LAST_DIGIT = 8;
public ContestScanner(java.io.InputStream in) {
this.in = in;
}
public ContestScanner() {
this(System.in);
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (java.io.IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
public boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new java.util.NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext())
throw new java.util.NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
int digit = b - '0';
if (n >= LONG_MAX_TENTHS) {
if (n == LONG_MAX_TENTHS) {
if (minus) {
if (digit <= LONG_MIN_LAST_DIGIT) {
n = -n * 10 - digit;
b = readByte();
if (!isPrintableChar(b)) {
return n;
} else if (b < '0' || '9' < b) {
throw new NumberFormatException(
String.format("%d%s... is not number", n, Character.toString(b)));
}
}
} else {
if (digit <= LONG_MAX_LAST_DIGIT) {
n = n * 10 + digit;
b = readByte();
if (!isPrintableChar(b)) {
return n;
} else if (b < '0' || '9' < b) {
throw new NumberFormatException(
String.format("%d%s... is not number", n, Character.toString(b)));
}
}
}
}
throw new ArithmeticException(
String.format("%s%d%d... overflows long.", minus ? "-" : "", n, digit));
}
n = n * 10 + digit;
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public long[] nextLongArray(int length) {
long[] array = new long[length];
for (int i = 0; i < length; i++)
array[i] = this.nextLong();
return array;
}
public long[] nextLongArray(int length, java.util.function.LongUnaryOperator map) {
long[] array = new long[length];
for (int i = 0; i < length; i++)
array[i] = map.applyAsLong(this.nextLong());
return array;
}
public int[] nextIntArray(int length) {
int[] array = new int[length];
for (int i = 0; i < length; i++)
array[i] = this.nextInt();
return array;
}
public int[][] nextIntArrayMulti(int length, int width) {
int[][] arrays = new int[width][length];
for (int i = 0; i < length; i++) {
for (int j = 0; j < width; j++)
arrays[j][i] = this.nextInt();
}
return arrays;
}
public int[] nextIntArray(int length, java.util.function.IntUnaryOperator map) {
int[] array = new int[length];
for (int i = 0; i < length; i++)
array[i] = map.applyAsInt(this.nextInt());
return array;
}
public double[] nextDoubleArray(int length) {
double[] array = new double[length];
for (int i = 0; i < length; i++)
array[i] = this.nextDouble();
return array;
}
public double[] nextDoubleArray(int length, java.util.function.DoubleUnaryOperator map) {
double[] array = new double[length];
for (int i = 0; i < length; i++)
array[i] = map.applyAsDouble(this.nextDouble());
return array;
}
public long[][] nextLongMatrix(int height, int width) {
long[][] mat = new long[height][width];
for (int h = 0; h < height; h++)
for (int w = 0; w < width; w++) {
mat[h][w] = this.nextLong();
}
return mat;
}
public int[][] nextIntMatrix(int height, int width) {
int[][] mat = new int[height][width];
for (int h = 0; h < height; h++)
for (int w = 0; w < width; w++) {
mat[h][w] = this.nextInt();
}
return mat;
}
public double[][] nextDoubleMatrix(int height, int width) {
double[][] mat = new double[height][width];
for (int h = 0; h < height; h++)
for (int w = 0; w < width; w++) {
mat[h][w] = this.nextDouble();
}
return mat;
}
public char[][] nextCharMatrix(int height, int width) {
char[][] mat = new char[height][width];
for (int h = 0; h < height; h++) {
String s = this.next();
for (int w = 0; w < width; w++) {
mat[h][w] = s.charAt(w);
}
}
return mat;
}
}
static class ContestPrinter extends java.io.PrintWriter {
public ContestPrinter(java.io.PrintStream stream) {
super(stream);
}
public ContestPrinter() {
super(System.out);
}
private static String dtos(double x, int n) {
StringBuilder sb = new StringBuilder();
if (x < 0) {
sb.append('-');
x = -x;
}
x += Math.pow(10, -n) / 2;
sb.append((long) x);
sb.append(".");
x -= (long) x;
for (int i = 0; i < n; i++) {
x *= 10;
sb.append((int) x);
x -= (int) x;
}
return sb.toString();
}
@Override
public void print(float f) {
super.print(dtos(f, 20));
}
@Override
public void println(float f) {
super.println(dtos(f, 20));
}
@Override
public void print(double d) {
super.print(dtos(d, 20));
}
@Override
public void println(double d) {
super.println(dtos(d, 20));
}
public void printArray(int[] array, String separator) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
super.print(array[i]);
super.print(separator);
}
super.println(array[n - 1]);
}
public void printArray(int[] array) {
this.printArray(array, " ");
}
public void printArray(int[] array, String separator, java.util.function.IntUnaryOperator map) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
super.print(map.applyAsInt(array[i]));
super.print(separator);
}
super.println(map.applyAsInt(array[n - 1]));
}
public void printArray(int[] array, java.util.function.IntUnaryOperator map) {
this.printArray(array, " ", map);
}
public void printArray(long[] array, String separator) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
super.print(array[i]);
super.print(separator);
}
super.println(array[n - 1]);
}
public void printArray(long[] array) {
this.printArray(array, " ");
}
public void printArray(long[] array, String separator, java.util.function.LongUnaryOperator map) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
super.print(map.applyAsLong(array[i]));
super.print(separator);
}
super.println(map.applyAsLong(array[n - 1]));
}
public void printArray(long[] array, java.util.function.LongUnaryOperator map) {
this.printArray(array, " ", map);
}
}
}