TIOJ 1341：[IOI 2007, Day 1] Aliens

TIOJ 1341：[IOI 2007, Day 1] Aliens

題目大意：在一個 $n\times n$ 的格子裡，有一塊 $5\times 5$ 的棋盤狀格子，邊長為 $m$，由以壓平和未壓平相間。你可以透過函式詢問 $(x,y)$ 是否有壓平，$n$ 小於等於 $2000000000$，限詢問 $300$ 次，最後要回傳棋盤的中心點。

解法：用加 $1$、加 $2$、加 $4...$ 尋找其中一格 $x$ 的最右座標，用同樣方法找 $x$ 最左座標、$y$ 的最下座標，因為是正方形，$y$ 的最上座標可以直接計算得到，再來因為棋盤只有 $5\times 5$，直接找就可以了。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <iostream>
#include "lib1341.h"
using namespace std;

#define LL long long

int n, x0, y00;
LL len;
int xl, xr, yb;

void solve() {
    int l = x0, r = n;
    for (LL i = 1; x0 + i <= n; i *= 2) {
        if (!Examine (x0 + i, y00)) {
            r = x0 + i - 1;
            break;
        }
    }
    while (l < r) {
        int mid = l + (r - l) / 2 + 1;
        if (Examine (mid, y00))
            l = mid;
        else
            r = mid - 1;
    }
    xr = l;

    l = 1, r = x0;
    for (LL i = 1; x0 - i > 0; i *= 2) {
        if (!Examine (x0 - i, y00)) {
            l = x0 - i + 1;
            break;
        }
    }
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (Examine (mid, y00))
            r = mid;
        else
            l = mid + 1;
    }
    xl = l;

    l = y00, r = n;
    for (LL i = 1; y00 + i <= n; i *= 2) {
        if (!Examine (x0, y00 + i)) {
            r = y00 + i - 1;
            break;
        }
    }
    while (l < r) {
        int mid = l + (r - l) / 2 + 1;
        if (Examine (x0, mid))
            l = mid;
        else
            r = mid - 1;
    }
    yb = l;

    len = xr - xl + 1;
    x0 = xr - len / 2;
    y00 = yb - len / 2;

    xr = x0 + (n - x0) / (2 * len) * (2 * len);
    xl = x0 - (x0 - 1) / (2 * len) * (2 * len);
    yb = y00 + (n - y00) / (2 * len) * (2 * len);
    for (LL i = x0 + 2 * len; i <= n; i += 2 * len)
        if (!Examine (i, y00)) {
            xr = i - 2 * len;
            break;
        }
    for (LL i = x0 - 2 * len; i > 0; i -= 2 * len)
        if (!Examine (i, y00)) {
            xl = i + 2 * len;
            break;
        }
    for (LL i = y00 + 2 * len; i <= n; i += 2 * len)
        if (!Examine (x0, i)) {
            yb = i - 2 * len;
            break;
        }
    Solution (xl + (xr - xl) / 2, yb - (xr - xl) / 2);
}

int main() {
    Init (&n, &x0, &y00);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！