結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2018-05-26 04:20:20 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 889 ms / 1,000 ms |
| コード長 | 6,516 bytes |
| コンパイル時間 | 30,809 ms |
| 実行使用メモリ | 23,628 KB |
| スコア | 29,511 |
| 最終ジャッジ日時 | 2018-05-26 04:20:53 |
|
ジャッジサーバーID （参考情報） |
judge10 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
import java.util.Arrays;
import java.util.Comparator;
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];
int[][] L_sort = new int[K][2];
curMap = new int[N][N];
for (int i = 0; i < K; ++i) {
L[i] = sc.nextInt();
L_sort[i][0] = L[i];
L_sort[i][1] = i;
}
Arrays.sort(L_sort, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
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];
{
int[][] dp = new int[N][N];
int[][] dp2 = new int[N][N];
for (int i = N - 1; i >= 0; --i) {
for (int j = 0; j < N; ++j) {
if (curMap[i][j] > 0)
dp[i][j] += (i + 1 < N ? dp[i + 1][j] : 0) + curMap[i][j];
if (curMap[j][i] > 0)
dp2[j][i] += (i + 1 < N ? dp[j][i + 1] : 0) + curMap[j][i];
}
}
boolean[] used = new boolean[K];
loop: for (int j = K - 1; j >= 0; --j) {
if (used[L_sort[j][1]])
continue;
for (long x = 0; x < N; ++x) {
for (long y = 0; y < N; ++y) {
if (x + L_sort[j][0] <= N && dp[(int) x][(int) y] >= L_sort[j][0]) {
long op = (y + 1) << 32 | (x + 1);
act(curMap, op, L_sort[j][0]);
used[L_sort[j][1]] = true;
list[L_sort[j][1]] = op;
{
for (int s = 0; s < N; ++s)
dp[s][(int) y] = 0;
for (int s = N - 1; s >= 0; --s) {
if (curMap[s][(int) y] > 0)
dp[s][(int) y] += (s + 1 < N ? dp[s + 1][(int) y] : 0) + curMap[s][(int) y];
}
}
continue loop;
}
if (y + L_sort[j][0] <= N && dp2[(int) x][(int) y] >= L_sort[j][0]) {
long op = (y + 1) << 32 | (x + 1);
act(curMap, -op, L_sort[j][0]);
used[L_sort[j][1]] = true;
list[L_sort[j][1]] = -op;
{
for (int s = 0; s < N; ++s)
dp2[(int) x][(int) s] = 0;
for (int s = N - 1; s >= 0; --s) {
if (curMap[(int) x][s] > 0)
dp2[(int) x][s] += (s + 1 < N ? dp2[(int) x][s + 1] : 0) + curMap[(int) x][s];
}
}
continue loop;
}
}
}
}
out: for (int i = 0; i < K; ++i) {
for (int j = K - 1; j > i; --j) {
if (used[L_sort[j][1]] || used[L_sort[i][1]])
continue;
int Len = L_sort[j][0] - L_sort[i][0];
for (long x = 0; x < N; ++x) {
for (long y = 0; y < N; ++y) {
if (x + L_sort[j][0] <= N && dp[(int) x][(int) y] >= Len) {
long opi = (y + 1) << 32 | (x + 1 + Len);
long opj = (y + 1) << 32 | (x + 1);
int cnt = 0;
cnt += act(curMap, opi, L_sort[i][0]);
cnt += act(curMap, opj, L_sort[j][0]);
list[L_sort[i][1]] = opi;
list[L_sort[j][1]] = opj;
used[L_sort[i][1]] = true;
used[L_sort[j][1]] = true;
{
for (int s = 0; s < N; ++s)
dp[s][(int) y] = 0;
for (int s = N - 1; s >= 0; --s) {
if (curMap[s][(int) y] > 0)
dp[s][(int) y] += (s + 1 < N ? dp[s + 1][(int) y] : 0) + curMap[s][(int) y];
}
}
continue out;
} else if (y + L_sort[j][0] <= N && dp2[(int) x][(int) y] >= Len) {
long opi = (y + 1 + Len) << 32 | (x + 1);
long opj = (y + 1) << 32 | (x + 1);
int cnt = 0;
cnt += act(curMap, -opi, L_sort[i][0]);
cnt += act(curMap, -opj, L_sort[j][0]);
list[L_sort[i][1]] = -opi;
list[L_sort[j][1]] = -opj;
used[L_sort[i][1]] = true;
used[L_sort[j][1]] = true;
{
for (int s = 0; s < N; ++s)
dp2[(int) x][s] = 0;
for (int s = N - 1; s >= 0; --s) {
if (curMap[(int) x][s] > 0)
dp2[(int) x][s] += (s + 1 < N ? dp2[(int) x][s + 1] : 0)
+ curMap[(int) x][s];
}
}
continue out;
}
}
}
}
}
for (int i = 0; i < K; ++i) {
if (used[i])
continue;
long op = rnd(L[i]);
list[i] = op;
act(curMap, list[i], L[i]);
}
}
for (int t = 0; t < 300000; ++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]);
}
System.out.println(getPt());
}
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));
}
}