結果

問題 No.5002 stick xor
ユーザー GrenacheGrenache
提出日時 2018-05-27 21:14:59
言語 Java21
(openjdk 21)
結果
AC  
実行時間 980 ms / 1,000 ms
コード長 3,141 bytes
コンパイル時間 31,733 ms
実行使用メモリ 85,084 KB
スコア 32,451
最終ジャッジ日時 2018-05-27 21:15:33
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 778 ms
78,152 KB
testcase_01 AC 828 ms
79,852 KB
testcase_02 AC 798 ms
83,304 KB
testcase_03 AC 825 ms
79,192 KB
testcase_04 AC 835 ms
84,520 KB
testcase_05 AC 811 ms
79,892 KB
testcase_06 AC 833 ms
83,172 KB
testcase_07 AC 787 ms
81,520 KB
testcase_08 AC 829 ms
77,576 KB
testcase_09 AC 830 ms
81,076 KB
testcase_10 AC 800 ms
82,476 KB
testcase_11 AC 816 ms
79,132 KB
testcase_12 AC 875 ms
75,144 KB
testcase_13 AC 878 ms
84,720 KB
testcase_14 AC 930 ms
83,344 KB
testcase_15 AC 980 ms
84,888 KB
testcase_16 AC 959 ms
82,944 KB
testcase_17 AC 965 ms
83,932 KB
testcase_18 AC 859 ms
78,136 KB
testcase_19 AC 850 ms
82,892 KB
testcase_20 AC 907 ms
81,788 KB
testcase_21 AC 820 ms
75,608 KB
testcase_22 AC 820 ms
80,632 KB
testcase_23 AC 778 ms
77,004 KB
testcase_24 AC 841 ms
83,384 KB
testcase_25 AC 842 ms
83,372 KB
testcase_26 AC 775 ms
77,452 KB
testcase_27 AC 865 ms
83,144 KB
testcase_28 AC 842 ms
78,572 KB
testcase_29 AC 832 ms
83,368 KB
testcase_30 AC 827 ms
83,564 KB
testcase_31 AC 824 ms
85,084 KB
権限があれば一括ダウンロードができます

ソースコード

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 < 2 && !pq.isEmpty(); j++) {
				Op e = pq.remove();

				for (int jj = 0; jj < 80; 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