結果
問題 | No.2731 Two Colors |
ユーザー | anago-pie |
提出日時 | 2024-04-27 16:16:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,256 ms / 3,000 ms |
コード長 | 2,848 bytes |
コンパイル時間 | 2,705 ms |
コンパイル使用メモリ | 220,112 KB |
実行使用メモリ | 120,832 KB |
最終ジャッジ日時 | 2024-11-15 19:51:26 |
合計ジャッジ時間 | 23,373 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,256 ms
120,832 KB |
testcase_01 | AC | 1,252 ms
120,832 KB |
testcase_02 | AC | 1,255 ms
120,832 KB |
testcase_03 | AC | 8 ms
6,816 KB |
testcase_04 | AC | 56 ms
9,088 KB |
testcase_05 | AC | 33 ms
6,816 KB |
testcase_06 | AC | 190 ms
18,304 KB |
testcase_07 | AC | 236 ms
22,912 KB |
testcase_08 | AC | 23 ms
6,820 KB |
testcase_09 | AC | 888 ms
78,208 KB |
testcase_10 | AC | 8 ms
6,820 KB |
testcase_11 | AC | 808 ms
61,952 KB |
testcase_12 | AC | 898 ms
78,208 KB |
testcase_13 | AC | 681 ms
53,376 KB |
testcase_14 | AC | 380 ms
34,944 KB |
testcase_15 | AC | 18 ms
6,816 KB |
testcase_16 | AC | 327 ms
27,520 KB |
testcase_17 | AC | 507 ms
41,728 KB |
testcase_18 | AC | 66 ms
9,216 KB |
testcase_19 | AC | 332 ms
28,288 KB |
testcase_20 | AC | 567 ms
53,504 KB |
testcase_21 | AC | 69 ms
9,728 KB |
testcase_22 | AC | 920 ms
74,752 KB |
testcase_23 | AC | 205 ms
19,584 KB |
testcase_24 | AC | 87 ms
11,264 KB |
testcase_25 | AC | 4 ms
6,816 KB |
testcase_26 | AC | 721 ms
63,104 KB |
testcase_27 | AC | 911 ms
77,056 KB |
testcase_28 | AC | 587 ms
45,056 KB |
testcase_29 | AC | 158 ms
15,872 KB |
testcase_30 | AC | 310 ms
28,672 KB |
testcase_31 | AC | 178 ms
17,024 KB |
testcase_32 | AC | 1,158 ms
86,912 KB |
testcase_33 | AC | 2 ms
6,820 KB |
testcase_34 | AC | 2 ms
6,816 KB |
testcase_35 | AC | 2 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<n; i++) #define debug 0 #define YES cout << "Yes" << endl; #define NO cout << "No" << endl; using ll = long long; using ld = long double; const int mod = 998244353; const int MOD = 1000000007; const double pi = atan2(0, -1); const int inf = 1 << 31 - 1; const ll INF = 1LL << 63-1; #include <time.h> #include <chrono> //vectorの中身を空白区切りで出力 template<typename T> void print1(vector<T> v) { for (int i = 0; i < v.size(); i++) { cout << v[i]; if (i < v.size() - 1) { cout << " "; } } } //vectorの中身を改行区切りで出力 template<typename T> void print2(vector<T> v) { for (auto x : v) { cout << x << endl; } } //二次元配列を出力 template<typename T> void printvv(vector<vector<T>> vv) { for (vector<T> v : vv) { print1(v); cout << endl; } } //vectorを降順にソート template<typename T> void rsort(vector<T> &v) { sort(v.begin(), v.end()); reverse(v.begin(), v.end()); } //昇順priority_queueを召喚 template<typename T> struct rpriority_queue { priority_queue<T, vector<T>, greater<T>> pq; void push(T x) { pq.push(x); } void pop() { pq.pop(); } T top() { return pq.top(); } size_t size() { return pq.size(); } bool empty() { return pq.empty(); } }; int main() { int H ,W; cin >> H >> W; vector<vector<int>> num(H, vector<int>(W)); rep(i, H) { rep(j, W) { cin >> num[i][j]; } } vector<vector<int>> col(H, vector<int>(W, -1)); col[0][0] = 1; col[H - 1][W - 1] = 0; map<int, vector<int>> mp; rep(i, H) { rep(j, W) { mp[num[i][j]] = { i,j }; } } set<int> z, o; o.insert(num[1][0]); o.insert(num[0][1]); z.insert(num[H - 1][W - 2]); z.insert(num[H - 2][W - 1]); int cnt = 0; while (1) { bool ed = false; if (cnt % 2 == 0) { int n = *begin(o); int x = mp[n][0]; int y = mp[n][1]; col[x][y] = 0; if (z.count(n)) { ed = true; } else { o.erase(n); if (x > 0 && col[x - 1][y] == -1) { o.insert(num[x - 1][y]); } if (x < H - 1 && col[x+1][y]==-1) { o.insert(num[x + 1][y]); } if (y > 0 && col[x][y - 1] == -1) { o.insert(num[x][y - 1]); } if (y < W - 1 && col[x][y + 1] == -1) { o.insert(num[x][y + 1]); } } } else { int n = *begin(z); int x = mp[n][0]; int y = mp[n][1]; col[x][y] = 1; if (o.count(n)) { ed = true; } else { z.erase(n); if (x > 0 && col[x - 1][y] == -1) { z.insert(num[x - 1][y]); } if (x < H - 1 && col[x + 1][y] == -1) { z.insert(num[x + 1][y]); } if (y > 0 && col[x][y - 1] == -1) { z.insert(num[x][y - 1]); } if (y < W - 1 && col[x][y + 1] == -1) { z.insert(num[x][y + 1]); } } } cnt++; if (ed) { break; } } cout << cnt << endl; }