Codeforces Round #312 Div2 D: Guess Your Way Out! II
解法
含む範囲のクエリは、重なっている部分だけを取り出していけば、必ず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); } }