Codeforces Round #Pi (Div. 2) D. One-Dimensional Battle Ships

Codeforces Round #Pi (Div. 2) は寝坊して不参加です。代わりに virtual participation やったら 4 完でした。

問題

Problem - 567D - Codeforces

解法

二分探索で解きました。

med個目までshotした時嘘を付いているとはっきりわかるならtrueを,そうでないならfalseを返す関数を作ります。これが程度でできるようにしたいです。

まず入力xをmed個目まででソートします。

Aliceが嘘をついていない可能性がある場合は1とx[0]の間,x[i]とx[i+1]の間,x[med-1]とnの間に少なくともk個の船が入っているはずです。これを計算して判定しましょう。

const int MAXM = 200200;
int x[MAXM];
int n, k, a;

bool ok(int med) {
    vector<int> q(med);
    for (int i = 0; i < med; i++) q[i] = x[i];
    sort(q.begin(), q.end());
    int cnt = 0;
    {
        int cur = 0;
        while (cur < q[0]) {
            cur += a;
            if (cur < q[0]) cnt++;
            cur += 1;
        }
    }
    for (int i = 0; i < med-1; i++) {
        int cur = q[i];
        while (cur < q[i+1]) {
            cur += a;
            if (cur < q[i+1]) cnt++;
            cur += 1;
        }
    }
    {
        int cur = q[med-1];
        while (cur <= n) {
            cur += a;
            if (cur <= n) cnt++;
            cur += 1;
        }
    }
    return cnt < k;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> k >> a;
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> x[i];
    }
    int low = 0, high = m;
    while (high - low > 1) {
        int med = (high + low) / 2;
        if (ok(med)) high = med;
        else low = med;
    }
    if (high == m && !ok(high)) cout << -1 << endl;
    else cout << high << endl;
    return 0;
}