結果
| 問題 | No.5002 stick xor |
| ユーザー |
 tanzaku
|
| 提出日時 | 2018-05-26 00:35:43 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,328 bytes |
| コンパイル時間 | 36,667 ms |
| スコア | 0 |
| 最終ジャッジ日時 | 2018-05-26 00:36:21 |
|
ジャッジサーバーID （参考情報） |
judge10 / |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 32 |
ソースコード
import java.util.*;public class Main {Stick[] sticks;int n;int k;int[][] board;final Random random = new Random(0);final int inf = 1<<29;void solve() {Timer timer = new Timer(900);try (Scanner in = new Scanner(System.in)) {n = in.nextInt();k = in.nextInt();board = new int[n][n];sticks = new Stick[k];for (int i = 0; i < k; i++) {sticks[i] = new Stick();sticks[i].len = in.nextInt();sticks[i].placed = false;}for (int i = 0; i < n; i++) {String s = in.next();for (int j = 0; j < n; j++) {board[i][j] = s.charAt(j) - '0';}}}Stick[] sortedStick = sticks.clone();Arrays.sort(sortedStick, Comparator.comparingInt(s -> -s.len));for (Stick s : sortedStick) {put(s);}int iterate = 0;while ((iterate++&0xFF) != 0 || !timer.signal()) {int idx = random.nextInt(k);if (sticks[idx].placed) {if (random.nextInt(k) != 0) {move(sticks[idx]);} else {put(sticks[idx]);}} else {put(sticks[idx]);}}for (Stick s : sticks) {if (s.dir == 0) {// System.out.printf("%d %d %d %d\n", s.x+1, s.y+1, s.x+s.len, s.y+1);System.out.printf("%d %d %d %d\n", s.y+1, s.x+1, s.y+1, s.x+s.len);} else {// System.out.printf("%d %d %d %d\n", s.x+1, s.y+1, s.x+1, s.y+s.len);System.out.printf("%d %d %d %d\n", s.y+1, s.x+1, s.y+s.len, s.x+1);}}}void move(Stick s) {int d = random.nextInt(2);while (moveCost(s, d) <= 0) {if (s.dir == 0) {if (d == 0) {board[s.y][s.x-1+s.len] ^= 1;board[s.y][s.x-1] ^= 1;s.x -= 1;} else {board[s.y][s.x+s.len] ^= 1;board[s.y][s.x] ^= 1;s.x += 1;}} else {if (d == 0) {board[s.y-1+s.len][s.x] ^= 1;board[s.y-1][s.x] ^= 1;s.y -= 1;} else {board[s.y+s.len][s.x] ^= 1;board[s.y][s.x] ^= 1;s.y += 1;}}}}int moveCost(Stick s, int d) {if (s.dir == 0) {int x0 = s.x + 2*d-1;if (x0 < 0 || x0 + s.len - 1 >= n) return inf;if (d == 0) {return (board[s.y][s.x - 1] ^ 1) - board[s.y][s.x + s.len - 1];} else {return (board[s.y][s.x + s.len] ^ 1) - board[s.y][s.x];}} else {int y0 = s.y + 2*d-1;if (y0 < 0 || y0 + s.len - 1 >= n) return inf;if (d == 0) {return (board[s.y - 1][s.x] ^ 1) - board[s.y + s.len - 1][s.x];} else {return (board[s.y + s.len][s.x] ^ 1) - board[s.y][s.x];}}}void put(Stick s) {if (s.placed) {flip(s);}int opt = -inf;List<Integer> place = new ArrayList<>();for (int y = 0; y < n; y++) {int sum = 0;for (int x = 0; x < n; x++) {sum += board[y][x];if (x >= s.len) sum -= board[y][x-s.len];if (x >= s.len - 1) {if (opt < sum) { opt = sum; place.clear(); }if (opt == sum) { place.add((y*n+(x-s.len+1))*2+0); }}}}for (int x = 0; x < n; x++) {int sum = 0;for (int y = 0; y < n; y++) {sum += board[y][x];if (y >= s.len) sum -= board[y-s.len][x];if (y >= s.len - 1) {if (opt < sum) { opt = sum; place.clear(); }if (opt == sum) { place.add(((y-s.len+1)*n+x)*2+1); }}}}int p = place.get(random.nextInt(place.size()));s.x = p / 2 % n;s.y = p / 2 / n;s.dir = p % 2;// dump(s.x, s.y, s.dir, s.len, opt);flip(s);}void flip(Stick s) {if (s.dir == 0) {for (int dx = 0; dx < s.len; dx++) board[s.y][s.x+dx] ^= 1;} else {for (int dy = 0; dy < s.len; dy++) board[s.y+dy][s.x] ^= 1;}s.placed = !s.placed;}public static void main(String[] args) {new Main().solve();}static void dump(Object... objects) {System.err.println(Arrays.deepToString(objects));}class Stick {boolean placed;int x, y, dir, len;}class Timer {long start;long time;public Timer(long time) {this.start = System.currentTimeMillis();this.time = time;}public void restart() {this.start = System.currentTimeMillis();}public long elapsed() {return System.currentTimeMillis() - this.start;}public double scaled() {return (this.start + this.time - System.currentTimeMillis()) / (double) this.time;}public boolean signal() {return System.currentTimeMillis() >= this.start + this.time;}}}