結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
		}
	}
}
0