CF 1498E Two Houses

题目描述

http://codeforces.com/problemset/problem/1498/E

Solution

我们考虑对于 $|k_v-k_u|$ 从大到小排序，每次询问 $u$ 是否能到 $v$，这里 $k_u<k_v$

如果 $u$ 能到 $v$ 一定能说明 $u$ 到 $v$ 位于同一 $scc$，那么直接输出答案即可

#include <iostream>
#include <algorithm>
#define maxn 1010
#define ll long long
using namespace std;

int n, d[maxn];

struct node {
    int x, y;

    friend bool operator < (const node &u, const node &v) { return d[u.x] - d[u.y] > d[v.x] - d[v.y]; }
} a[maxn * maxn]; int cnt; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> d[i];
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            a[++cnt] = { i, j };
    for (int i = 1; i <= cnt; ++i)
        if (d[a[i].x] < d[a[i].y]) swap(a[i].x, a[i].y);
    sort(a + 1, a + cnt + 1);
    for (int i = 1; i <= cnt; ++i) {
        int x = a[i].x, y = a[i].y; string s;
        cout << "? " << x << " " << y << endl;
        cin >> s;
        if (s == "Yes") return cout << "! " << x << " " << y << endl, 0;
    } cout << "! 0 0" << endl;
    return 0; 
}