LISGRID [yukicoder 918]

https://yukicoder.me/problems/no/918

前提知識

• トポロジカルソート

解説

https://yukicoder.me/submissions/393911

Eのお絵かきのようす pic.twitter.com/oeQdMigeea

— satanic@競プロ🔥 (@satanic0258) October 25, 2019

天才だ…わかり易すぎる

どう手をつけていいかわからない問題構築では、ある種の仮定をすることで解けるようになってくる。
今回であれば、最長増加列は前半部分に昇順で作り、後半は降順にする。
あと、数列A,Bは降順の状態で考えることにする。
すると、結果的に作られる大小関係は、satanicさんのような図になる。
賢い。

あとは、この大小関係を満たすように順列を割り当てていくだけだが、これにはトポロジカルソートを使おう。
ソート順で大きい数から割り当てていけば、構築できる。

int H, W, A[404], B[404];
int ans[404][404];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> A[y];
    rep(x, 0, W) cin >> B[x];

    sort(A, A + H, greater<int>());
    sort(B, B + W, greater<int>());

    TopologicalSort ts(H * W);
    rep(y, 0, H) {
        rep(x, 0, A[y] - 1) ts.add_edge(y * W + x, y * W + x + 1);
        rep(x, A[y] - 1, W - 1) ts.add_edge(y * W + x + 1, y * W + x);
    }
    rep(x, 0, W) {
        rep(y, 0, B[x] - 1) ts.add_edge(y * W + x, (y + 1) * W + x);
        rep(y, B[x] - 1, H - 1) ts.add_edge((y + 1) * W + x, y * W + x);
    }

    vector<int> ord;
    bool res = ts.sort(ord);
    assert(res);

    int num = 1;
    fore(i, ord) {
        int x = i % W;
        int y = i / W;

        ans[y][x] = num;
        num++;
    }

    rep(y, 0, H) {
        rep(x, 0, W) {
            if(x) printf(" ");
            printf("%d", ans[y][x]);
        }
        printf("\n");
    }
}