結果

問題 No.5002 stick xor
コンテスト
ユーザー Grenache
提出日時 2018-05-27 20:38:05
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 3,142 bytes
コンパイル時間 7,346 ms
実行使用メモリ 89,828 KB
スコア 0
最終ジャッジ日時 2018-05-27 20:38:34
ジャッジサーバーID
（参考情報） 		judge7 /
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;


public class Main_yukicoder5002_1 {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();
		int k = sc.nextInt();

		int[] l = new int[k];
		for (int i = 0; i < k; i++) {
			l[i] = sc.nextInt();
		}

		List<Long> a = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			long tmp = 0;
			char[] s = sc.next().toCharArray();
			for (int j = 0; j < n; j++) {
				if (s[j] == '1') {
					tmp |= 0x1L << j;
				}
			}

			a.add(tmp);
		}

		Random rnd = new Random(0);
		PriorityQueue<Op> pq = new PriorityQueue<>();
		pq.add(new Op(a));
		for (int i = 0; i < k; i++) {
			PriorityQueue<Op> pq2 = new PriorityQueue<>();
			for (int j = 0; j < 3 && !pq.isEmpty(); j++) {
				Op e = pq.remove();

				for (int jj = 0; jj < 200; jj++) {
					int x = rnd.nextInt(n);
					int y = rnd.nextInt(n);

					if (x + l[i] - 1 < n) {
						Op tmp = e.copy();
						for (int ii = x; ii < x + l[i]; ii++) {
							tmp.a.set(y, tmp.a.get(y) ^ 0x1L << ii);
						}
						tmp.set(tmp.a, false, x, y);

//						if (tmp.score <= e.score + Math.max(3, l[i] / 2)) {
						pq2.add(tmp);
//						}
					}

					if (y + l[i] - 1 < n) {
						Op tmp = e.copy();
						for (int ii = y; ii < y + l[i]; ii++) {
							tmp.a.set(ii, tmp.a.get(ii) ^ 0x1L << x);
						}
						tmp.set(tmp.a, true, x, y);

//						if (tmp.score <= e.score + Math.max(3, l[i] / 2)) {
						pq2.add(tmp);
//						}
					}
				}
			}

			pq = pq2;
		}

		Op e = pq.remove();
//		for (long ee : e.a) {
//			pr.println(ee);
//		}
//		pr.println(e.score);

		for (int i = 0; i < k; i++) {
			boolean d = e.d.get(i);
			int x = e.x.get(i);
			int y = e.y.get(i);

			if (!d) {
				pr.printf("%d %d %d %d\n", y + 1, x + 1, y + 1, x + l[i]);
			} else {
				pr.printf("%d %d %d %d\n", y + 1, x + 1, y + l[i], x + 1);
			}
		}
	}

	static class Op implements Comparable<Op> {
		List<Long> a;
		int score;
		List<Boolean> d;
		List<Integer> x;
		List<Integer> y;

		private Op() {
		}

		Op(List<Long> a) {
			this.a = a;
			for (long e : a) {
				score += Long.bitCount(e);
			}
			d = new ArrayList<>();
			x = new ArrayList<>();
			y = new ArrayList<>();
		}

		void set(List<Long> a, boolean d, int x, int y) {
			this.a = a;
			score = 0;
			for (long e : a) {
				score += Long.bitCount(e);
			}
			this.d.add(d);
			this.x.add(x);
			this.y.add(y);
		}

		Op copy() {
			Op tmp = new Op();

			tmp.a = new ArrayList<>(this.a);
			tmp.score = this.score;
			tmp.d = new ArrayList<>(this.d);
			tmp.x = new ArrayList<>(this.x);
			tmp.y = new ArrayList<>(this.y);

			return tmp;
		}

		@Override
		public int compareTo(Op o) {
			return Integer.compare(score, o.score);
		}
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(INPUT == null ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
		pr = new Printer(System.out);

		solve();

//		pr.close();
		pr.flush();
//		sc.close();
	}

	static String INPUT = null;

	private static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}
0