Codeforces Round #331 (Div. 2) C. Wilbur and Points

問題

codeforces.com

解法

とりあえず誤読してないかを確認しましょう。僕は
Also, it is guaranteed that if some point (x, y) is present in the input, then all points (x', y'), such that 0 ≤ x' ≤ x and 0 ≤ y' ≤ y, are also present in the input.
を見逃していました。

要するに, 各点がいずれかの w[i] と対応していなければならないので, まずそれらを対応させましょう。
で, それが aesthetically pleasing であるかを確かめれば良いです。

const int MAXN = 100100;
int w[MAXN];

void no() {
    cout << "NO" << endl;
    exit(0);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    map<int, vector<pii> > M;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        M[y-x].push_back(pii(x, y));
    }
    for (auto& p : M) {
        sort(p.second.begin(), p.second.end());
    }
    map<int, vector<int> > W;
    for (int i = 0; i < n; i++) {
        int w;
        cin >> w;
        W[w].push_back(i);
    }
    vector<pii> ans(n);
    for (auto p : W) {
        int w = p.first;
        if (p.second.size() != M[w].size()) no();
        int k = 0;
        for (int el : p.second) ans[el] = M[w][k++];
    }
    map<pii, int> X;
    for (int i = 0; i < n; i++) X[ans[i]] = i+1;
    for (auto p : X) {
        int x = p.first.first, y = p.first.second;
        int nx = x+1, ny = y+1;
        if (X.find(pii(nx, y)) != X.end() and X[pii(nx, y)] < p.second) no();
        if (X.find(pii(x, ny)) != X.end() and X[pii(x, ny)] < p.second) no();
    }
    cout << "YES" << endl;
    for (int i = 0; i < n; i++) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }
    return 0;
}