【ABC213】 C - Reorder Cards

atcoder.jp

解法

行に対して操作を行った場合、列には何も影響を及ぼさないことから、行と列は別々に考えても問題ないことがわかる。
今回問われているのは、どの要素も使用してない行や列を全て削除したときに、それぞれの要素の座標はどうなるか？ということなので、考えるのはそれぞれの要素の相対的な位置関係である。
行と列を分けた配列を新たに用意し、それぞれ昇順にソートして、前から順番に新しい座標を割り振れば良い。
ただし、同じ行・列に複数の要素が存在する場合に注意が必要。

本番での実装

座標圧縮を意識せずに書いたので、長々と書きすぎた気がする。

void solve(long long H, long long W, long long N, std::vector<long long> A, std::vector<long long> B) {
    vector<pair<ll, ll>> h, w; // ソートするための配列
    vector<pair<ll, ll>> ans(N); // 答え
    REP (i, N) {
        h.push_back({A[i], i});
        w.push_back({B[i], i});
    }
    ALL(sort, h); ALL(sort, w); // 昇順ソート

    ll preh = h[0].first;
    ll prew = w[0].first;
    ll cnth = 1, cntw = 1; // 要素に割り振る座標
    ans[h[0].second].first = cnth;
    ans[w[0].second].second = cntw;

    REP (i, N-1) {
　　// 一つ前の要素と一致している場合、座標を変化させない
        if (h[i].first != h[i+1].first) cnth++;
        if (w[i].first != w[i+1].first) cntw++;

        ans[h[i+1].second].first = cnth;
        ans[w[i+1].second].second = cntw;
    }

    REP (i, N) cout << ans[i].first << " " << ans[i].second << endl;
}