結果

問題 No.5002 stick xor
ユーザー 37zigen37zigen
提出日時 2018-05-25 23:56:44
言語 Java
(openjdk 23)
結果
AC  
実行時間 874 ms / 1,000 ms
コード長 2,951 bytes
コンパイル時間 29,807 ms
実行使用メモリ 22,380 KB
スコア 1,545
最終ジャッジ日時 2018-05-25 23:57:16
ジャッジサーバーID
(参考情報)
judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
int N;
int[][] curMap;
int[][] A;
void run() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int K = sc.nextInt();
int[] L = new int[K];
curMap = new int[N][N];
for (int i = 0; i < K; ++i)
L[i] = sc.nextInt();
A = new int[N][N];
for (int i = 0; i < N; ++i) {
char[] cs = sc.next().toCharArray();
for (int j = 0; j < N; ++j) {
A[i][j] = (int) (cs[j] - '0');
}
curMap[i] = Arrays.copyOf(A[i], A[i].length);
}
long[] list = new long[K];
for (int i = 0; i < K; ++i) {
long op = rnd(L[i]);
list[i] = op;
// while (act(curMap, op, L[i]) < 0) {
// act(curMap, op, L[i]);
// op = rnd(L[i]);
// }
}
for (int t = 0; t < 500000; ++t) {
int i = (int) (Math.random() * K);
int j = (int) (Math.random() * K);
if (i == j)
continue;
long opi = rnd(L[i]);
long opj = rnd(L[j]);
if (act(curMap, list[i], L[i]) + act(curMap, list[j], L[j]) + act(curMap, opi, L[i])
+ act(curMap, opj, L[j]) > 0) {
list[i] = opi;
list[j] = opj;
} else {
act(curMap, list[i], L[i]);
act(curMap, list[j], L[j]);
act(curMap, opi, L[i]);
act(curMap, opj, L[j]);
}
}
for (int i = 0; i < K; ++i) {
out(list[i], L[i]);
}
}
int act(int[][] map, long op, int L) {
int ret = 0;
int sign = (int) (op / Math.abs(op));
op = Math.abs(op);
int px = (int) op;
int py = (int) (op >> 32);
if (sign == 1) {
for (int i = px; i <= px + L - 1; ++i) {
for (int j = py; j <= py; ++j) {
if (curMap[i - 1][j - 1] == 1)
++ret;
else
--ret;
curMap[i - 1][j - 1] ^= 1;
}
}
} else {
for (int i = px; i <= px; ++i) {
for (int j = py; j <= py + L - 1; ++j) {
if (curMap[i - 1][j - 1] == 1)
++ret;
else
--ret;
curMap[i - 1][j - 1] ^= 1;
}
}
}
return ret;
}
long rnd(int L) {
while (true) {
long px = (long) (Math.random() * N) + 1;
long py = (long) (Math.random() * N) + 1;
if (px + L <= N + 1) {
return (px | (py << 32));
} else if (py + L <= N + 1) {
return (-(px | py << 32));
} else {
continue;
}
}
}
int getPt() {
int ret = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (A[i][j] == 0)
--ret;
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (curMap[i][j] == 0)
++ret;
}
}
return ret;
}
void out(long a, int L) {
int sign = (int) (a / Math.abs(a));
a = Math.abs(a);
int px = (int) a;
int py = (int) (a >> 32);
if (sign == 1) {
System.out.println(px + " " + py + " " + (px + L - 1) + " " + py);
} else {
System.out.println(px + " " + py + " " + px + " " + (py + L - 1));
}
}
public static void main(String[] args) {
new Main().run();
}
void tr(Object... objects) {
System.out.println(Arrays.deepToString(objects));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0