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

Codeforces Round #331 (Div. 2) に参加しました。 AB しか解けず撃沈。C は誤読して難しい問題を解いていたようでアレですが, それに気づいてからも実装に時間がかかるなどしてやっぱり実装力無いなぁと。

問題

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;
}