結果
問題 | No.918 LISGRID |
ユーザー |
![]() |
提出日時 | 2019-10-25 23:01:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 2,405 bytes |
コンパイル時間 | 2,022 ms |
コンパイル使用メモリ | 186,788 KB |
実行使用メモリ | 13,568 KB |
最終ジャッジ日時 | 2024-09-13 06:55:01 |
合計ジャッジ時間 | 5,274 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
//// Created by yamunaku on 2019/10/25.//#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(int i = 0; i < (n); i++)#define repl(i, l, r) for(int i = (l); i < (r); i++)#define per(i, n) for(int i = ((n)-1); i >= 0; i--)#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)#define all(x) (x).begin(),(x).end()#define MOD9 998244353#define MOD1 1000000007#define IINF 1000000000#define LINF 1000000000000000000#define SP <<" "<<#define CYES cout<<"Yes"<<endl#define CNO cout<<"No"<<endl#define CFS cin.tie(0);ios::sync_with_stdio(false)#define CST(x) cout<<fixed<<setprecision(x)typedef long long ll;typedef long double ld;typedef vector<int> vi;typedef vector<vector<int>> mti;typedef vector<ll> vl;typedef vector<vector<ll>> mtl;int main(){int h, w;cin >> h >> w;vi a(h), b(w);rep(i, h) cin >> a[i], a[i]--;rep(j, w) cin >> b[j], b[j]--;sort(all(a),greater<int>()), sort(all(b),greater<int>());vector<vector<vector<pair<int, int>>>> e(h, vector<vector<pair<int, int>>>(w));vector<vector<int>> deg(h, vector<int>(w, 0));rep(i, h){rep(j, w){if(i>0){if(i<=b[j]){e[i][j].push_back({i-1, j});deg[i-1][j]++;}}if(i<h-1){if(i>=b[j]){e[i][j].push_back({i+1, j});deg[i+1][j]++;}}if(j>0){if(j<=a[i]){e[i][j].push_back({i, j-1});deg[i][j-1]++;}}if(j<w-1){if(j>=a[i]){e[i][j].push_back({i, j+1});deg[i][j+1]++;}}}}int t = h * w;mti ans(h, vi(w, -1));queue<pair<int, int>> q;rep(i,h){rep(j,w){if(deg[i][j]==0) q.push({i,j});}}while(!q.empty()){auto now = q.front();q.pop();ans[now.first][now.second] = t;t--;for(auto &nx:e[now.first][now.second]){deg[nx.first][nx.second]--;if(deg[nx.first][nx.second] == 0) q.push(nx);}}rep(i, h){rep(j, w){cout << ans[i][j] << " ";}cout << endl;}return 0;}