結果
問題 | No.5002 stick xor |
ユーザー |
|
提出日時 | 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 |
ソースコード
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));}}