結果
問題 | No.918 LISGRID |
ユーザー |
![]() |
提出日時 | 2019-10-25 23:10:42 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,279 bytes |
コンパイル時間 | 1,251 ms |
コンパイル使用メモリ | 68,772 KB |
実行使用メモリ | 15,132 KB |
最終ジャッジ日時 | 2024-09-13 08:23:28 |
合計ジャッジ時間 | 4,572 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#define llint long longusing namespace std;llint h, w;llint a[405], b[405];llint ans[405][405];vector<llint> G[200005];vector<int> topo;bool used[200005];void tpsort(int v){used[v] = true;for(int i = 0; i < G[v].size(); i++){if(!used[G[v][i]]) tpsort(G[v][i]);}topo.push_back(v);}llint get(llint r, llint c){return r * w + c;}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> h >> w;for(int i = 0; i < h; i++) cin >> a[i], a[i]--;for(int i = 0; i < w; i++) cin >> b[i], b[i]--;sort(a, a+h);sort(b, b+w);for(int i = 0; i < h; i++){for(int j = a[i]-1; j >= 0; j--) G[get(i, j)].push_back(get(i, j+1));for(int j = a[i]+1; j < w; j++) G[get(i, j)].push_back(get(i, j-1));}for(int i = 0; i < w; i++){for(int j = b[i]-1; j >= 0; j--) G[get(j, i)].push_back(get(j+1, i));for(int j = b[i]+1; j < h; j++) G[get(j, i)].push_back(get(j-1, i));}for(int i = 0; i < h*w; i++) if(!used[i]) tpsort(i);reverse(topo.begin(), topo.end());for(int i = 0; i < topo.size(); i++){int v = topo[i];ans[v/w][v%w] = i+1;}for(int i = 0; i < h; i++){for(int j = 0; j < w; j++){cout << ans[i][j] << " ";}cout << endl;}return 0;}