結果

問題 No.5002 stick xor
コンテスト
ユーザー tsukammo
提出日時 2018-05-26 00:39:01
言語 Java
(openjdk 23)
結果
AC  
実行時間 955 ms / 1,000 ms
コード長 4,873 bytes
コンパイル時間 33,236 ms
実行使用メモリ 24,168 KB
スコア 36,873
最終ジャッジ日時 2018-05-26 00:39:51
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

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, W = 25;
	int[] L;
	boolean[][] map;
	Rect[] rs;

	void solve() {
		input();
		init();
		simulate(); // new
		if (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;
			}
			c++;

			int id = rnd.nextInt(K);
			Rect r = rs[id];
			int d = rnd.nextInt(2);
			int x, y;
			if (d == 0) {
				x = rnd.nextInt(N - r.w);
				y = rnd.nextInt(N);
			} else {
				x = rnd.nextInt(N);
				y = rnd.nextInt(N - r.w);
			}
			int ex = x + r.w * dx[d];
			int ey = y + r.w * dy[d];
			tmpScore = evalChange(x, y, d, r);

			if (tmpScore <= 0 || Line > tmpScore * rnd.nextDouble()) {
				score += tmpScore;
				// update
				r.x = x;
				r.y = y;
				r.d = d;
				if (tmpScore < 0) {
					u++;
				}
				//System.err.println("update:" + score);
			} else {
				// rollback
				// before
				ex = 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];
				}
				// after
				ex = x;
				ey = y;
				for (int i = 0; i <= r.w; i++) {
					map[ey][ex] = !map[ey][ex];
					ex += dx[d];
					ey += dy[d];
				}
			}
		}
		System.err.println("End  :" + (score));
		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;
		// before
		int 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];
		}
		// after
		ex = 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(4);
			int ex = x + w * dx[d];
			int ey = y + w * dy[d];
			if (outMap(ex, ey)) {
				if (outMap(ex, ey)) {
					if (d > 1) {
						d -= 2;
					} else {
						d += 2;
					}
				}
			}
			ex = x;
			ey = y;
			// flip
			for (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;
}
0