Codeforces Round #312 Div2 D: Guess Your Way Out! II

問題

codeforces.com

解法

含む範囲のクエリは、重なっている部分だけを取り出していけば、必ず1つだけの範囲になるはず。離れた2つの範囲が出てきた場合、題意に合わないのでcheatである。

含まない範囲のクエリは、和集合を取っていき、先に求めた含む範囲に合わせて見る。含む範囲を分断する形の時は2つ以上の答が存在してしまうのでnot sufficientを返す。

これらの処理を終えて、含む範囲に1つだけ数字が含まれていればそれを返す。

コード

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		long H = scanner.nextLong();
		long Q = scanner.nextLong();

		ArrayList<Query> includeQueries = new ArrayList<>();
		ArrayList<Query> excludeQueries = new ArrayList<>();
		for (int q = 0; q < Q; q++) {
			long h = scanner.nextLong();
			long L = scanner.nextLong();
			long R = scanner.nextLong();

			// クエリの範囲を最下段での範囲に変換しておく
			for (int i = 0; i < H - h; i++) {
				L *= 2;
				R *= 2;
				R++;
			}

			long isContain = scanner.nextLong();
			Query query = new Query(L, R);
			if (isContain == 1) {
				includeQueries.add(query);
			} else {
				excludeQueries.add(query);
			}
		}
		scanner.close();

		// 全てのinクエリが重なっている範囲を求める
		Collections.sort(includeQueries);
		long inL = (long) Math.pow(2, H - 1);
		long inR = (long) Math.pow(2, H) - 1;
		for (Query query : includeQueries) {
			if (inR < query.start || inL > query.end) {
				// 重なっている範囲が離れている場合、2つ以上答えが存在するため不適
				System.out.println("Game cheated!");
				return;
			}
			inL = Math.max(inL, query.start);
			inR = Math.min(inR, query.end);
		}

		Collections.sort(excludeQueries);
		ArrayDeque<Query> exDeque = new ArrayDeque<>(excludeQueries);
		while (!exDeque.isEmpty()) {
			// 重なりあったexを全てつなげる
			Query query = exDeque.poll();
			long exL = query.start;
			long exR = query.end;
			while (!exDeque.isEmpty() && exDeque.peek().start <= exR + 1) {
				exR = Math.max(exR, exDeque.poll().end);
			}

			if (inR < exL || exR < inL) {
				// 含む区間と含まない区間が交差しない時はスルー
				continue;
			}

			if (exL <= inL) {
				// 含まない区間が含む区間の前にかぶっているときは、含む区間を削る
				inL = exR + 1;
			}
			if (exR >= inR) {
				// 後ろにかぶっている時も同様
				inR = exL - 1;
			}

			if (inL > inR) {
				// 含む区間が全てexクエリに覆われてしまった場合
				System.out.println("Game cheated!");
				return;
			}

			if (inL < exL && exR < inR) {
				// 含まない範囲が、含む範囲を分断する場合、答えが複数存在してしまう
				System.out.println("Data not sufficient!");
				return;
			}
		}

		if (inL == inR) {
			// 答えが一意に定まる時
			System.out.println(inL);
		} else {
			// 含む範囲が2個以上の数字を含む時
			System.out.println("Data not sufficient!");
		}

	}

	public static void main(String[] args) {
		new Main().solve();
	}

}

class Query implements Comparable<Query> {
	long start, end;

	public Query(long s, long e) {
		this.start = s;
		this.end = e;
	}

	@Override
	public int compareTo(Query o) {
		if (this.start == o.start) {
			return Long.signum(this.end - o.end);
		}
		return Long.signum(this.start - o.start);
	}

}