結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-26 00:08:36 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 968 ms / 1,000 ms |
コード長 | 4,683 bytes |
コンパイル時間 | 35,841 ms |
実行使用メモリ | 24,108 KB |
スコア | 36,789 |
最終ジャッジ日時 | 2018-05-26 00:09:14 |
ジャッジサーバーID (参考情報) |
judge8 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
import java.io.IOException;import java.util.Scanner;/*** yukicoder** @author tsukammo*/public class Main {Scanner sc = new Scanner(System.in);Random rnd = new Random(19881221L);long st, et;int first;public static void main(String[] args) throws IOException {new Main().solve();}// 制約static int N = 60, K = 500, NN = N * N;int[] L;boolean[][] map;Rect[] rs;void solve() {input();init();simulate(); // newif (submit) {output();}}void init() {rs = new Rect[K];for (int i = 0; i < K; i++) {rs[i] = new Rect(i, L[i] - 1);}if (submit) {return;}}void simulate() {System.err.println("First:" + (first));int score = evalAll();System.err.println("Start:" + (score));long currentTime = System.currentTimeMillis();double C = TEMP * TL;double Line = 0.0;int tmpScore = 0;int c = 0, u = 0;while (currentTime < et) {if (c % 1000 == 0) {currentTime = System.currentTimeMillis();Line = (et - currentTime) / C;}int id = rnd.nextInt(K);Rect r = rs[id];int x = rnd.nextInt(N);int y = rnd.nextInt(N);int d = rnd.nextInt(2);int ex = x + r.w * dx[d];int ey = y + r.w * dy[d];if (outMap(ex, ey)) {d = d + 2;}tmpScore = evalChange(x, y, d, r);if (tmpScore <= 0 || Line > tmpScore * rnd.nextDouble()) {score += tmpScore;// updater.x = x;r.y = y;r.d = d;if (tmpScore < 0) {u++;}//System.err.println("update:" + score);} else {// rollback// beforeex = r.x;ey = r.y;for (int i = 0; i <= r.w; i++) {map[ey][ex] = !map[ey][ex];ex += dx[r.d];ey += dy[r.d];}// afterex = x;ey = y;for (int i = 0; i <= r.w; i++) {map[ey][ex] = !map[ey][ex];ex += dx[d];ey += dy[d];}}c++;}score = evalAll();System.err.println("End :" + (score));System.err.println("Last :" + (first - score) + " loop:" + c + " up:" + u);}int evalChange(int x, int y, int d, Rect r) {int ret = 0;// beforeint ex = r.x;int ey = r.y;for (int i = 0; i <= r.w; i++) {if (map[ey][ex]) {ret--;} else {ret++;}map[ey][ex] = !map[ey][ex];ex += dx[r.d];ey += dy[r.d];}// afterex = x;ey = y;for (int i = 0; i <= r.w; i++) {if (map[ey][ex]) {ret--;} else {ret++;}map[ey][ex] = !map[ey][ex];ex += dx[d];ey += dy[d];}return ret;}int evalAll() {int ret = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (map[i][j]) {ret++;}}}return ret;}final static int dx[] = new int[] { 1, 0, -1, 0 };final static int dy[] = new int[] { 0, 1, 0, -1 };boolean outMap(int x, int y) {return !(x > -1 && y > -1 && x < N && y < N);}void input() {N = sc.nextInt();st = System.currentTimeMillis();et = st + TL;K = sc.nextInt();L = new int[K];for (int i = 0; i < K; i++) {L[i] = sc.nextInt();}sc.nextLine();map = new boolean[N][N];first = 0;for (int i = 0; i < N; i++) {String tmp = sc.nextLine();char[] cl = tmp.toCharArray();for (int j = 0; j < N; j++) {if (cl[j] == '1') {map[i][j] = true;first++;}}}}class Rect {int id;int x, y, d;int w;public Rect(int id, int w) {this.id = id;this.w = w;this.x = rnd.nextInt(N);this.y = rnd.nextInt(N);this.d = rnd.nextInt(2);int ex = x + w * dx[d];int ey = y + w * dy[d];if (outMap(ex, ey)) {d = d + 2;}ex = x;ey = y;// flipfor (int i = 0; i <= w; i++) {map[ey][ex] = !map[ey][ex];ex += dx[d];ey += dy[d];}}public String toString() {int sx = x + 1;int sy = y + 1;int ex = sx + w * dx[d];int ey = sy + w * dy[d];if (d > 1) {sx = ex;sy = ey;d -= 2;ex = sx + w * dx[d];ey = sy + w * dy[d];}return sy + " " + sx + " " + ey + " " + ex;}}class Random {private long seed;private final long multiplier = 0x5DEECE66DL, addend = 0xBL, mask = (1L << 48) - 1;int bits, val;Random(long seed) {this.seed = seed;}int nextInt(int n) {do {bits = (int) ((seed = (seed * multiplier + addend) & mask) >>> 17);val = bits % n;} while (bits - val + (n - 1) < 0);return val;}double nextDouble() {return nextInt(10000000) / 10000000.0;}}void output() {for (int i = 0; i < K; i++) {System.out.println(rs[i].toString());}}final double TEMP = 10000;static final long TL = 800;static boolean submit = true;}