ABC269-E Last Rook

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        int StaX = 1;
        int EndX = N;
        int StaY = 1;
        int EndY = N;

        for (int I = 1; I <= 10; I++) {
            if (StaX < EndX) {
                int MidX = (StaX + EndX) / 2;
                int RangeX = MidX - StaX + 1;
                Console.WriteLine("? {0} {1} {2} {3}", 1, N, StaX, MidX);

                int GetCnt = int.Parse(Console.ReadLine());
                if (GetCnt < RangeX) {
                    EndX = MidX;
                }
                else {
                    StaX = MidX + 1;
                }
            }
        }

        for (int I = 1; I <= 10; I++) {
            if (StaY < EndY) {
                int MidY = (StaY + EndY) / 2;
                int RangeY = MidY - StaY + 1;
                Console.WriteLine("? {0} {1} {2} {3}", StaY, MidY, 1, N);

                int GetCnt = int.Parse(Console.ReadLine());
                if (GetCnt < RangeY) {
                    EndY = MidY;
                }
                else {
                    StaY = MidY + 1;
                }
            }
        }
        Console.WriteLine("! {0} {1}", StaY, StaX);
    }
}

解説

20回聞けて制約が1000以下で
2の10乗は1024なので、横で10回、縦で10回聞きます。

横幅が1000とすると
1から500に何個ルークがあるか聞いて、
500個なら、501から1000が候補
500個未満なら、1から500が候補
と絞っていけば良いです。