Codeforces #71 B "Colorful Field"

問題：http://codeforces.com/contest/79/problem/B

幅と高さと使えないセルの座標と求めるべき座標が与えられる．左上を(0.0)とするとき，右に向かってCarrot，Kiwi，Grapeとして，それを次の行に継続して適用してゆくとき，求めるべき座標にあるものを求める．

4000x4000の幅と高さと勘違いしてそのまま二次元配列で実装したらPretest4でMLE．よくみたら40000x40000だったので行番号x幅+列番号で一次元化して，その座標までの使えないセルの数を考慮して求めた．

コード

import java.util.*;

public class B {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt(), m = s.nextInt(), k = s.nextInt(), t = s.nextInt();
		int[] is = new int[k];
		for (int i = 0; i < k; ++i) {
			is[i] = (s.nextInt() - 1) * m + s.nextInt() - 1;
		}
		Arrays.sort(is);
		String[] r = { "Carrots", "Kiwis", "Grapes" };
		for (; t-- > 0;) {
			int key = (s.nextInt() - 1) * m + s.nextInt() - 1;
			if (Arrays.binarySearch(is, key) >= 0) {
				System.out.println("Waste");
				continue;
			}
			int c = 0;
			for (; c < is.length && is[c] < key; ++c)
				;
			System.out.println(r[(key - c) % 3]);
		}
	}
}