結果
問題 | No.2731 Two Colors |
ユーザー | anago-pie |
提出日時 | 2024-04-27 16:16:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,208 ms / 3,000 ms |
コード長 | 2,848 bytes |
コンパイル時間 | 2,279 ms |
コンパイル使用メモリ | 221,040 KB |
実行使用メモリ | 120,960 KB |
最終ジャッジ日時 | 2024-04-27 16:17:09 |
合計ジャッジ時間 | 20,984 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,205 ms
120,960 KB |
testcase_01 | AC | 1,187 ms
120,704 KB |
testcase_02 | AC | 1,208 ms
120,704 KB |
testcase_03 | AC | 6 ms
6,944 KB |
testcase_04 | AC | 57 ms
9,088 KB |
testcase_05 | AC | 27 ms
6,944 KB |
testcase_06 | AC | 153 ms
18,304 KB |
testcase_07 | AC | 200 ms
22,784 KB |
testcase_08 | AC | 21 ms
6,940 KB |
testcase_09 | AC | 843 ms
78,208 KB |
testcase_10 | AC | 8 ms
6,940 KB |
testcase_11 | AC | 747 ms
61,952 KB |
testcase_12 | AC | 846 ms
78,080 KB |
testcase_13 | AC | 623 ms
53,376 KB |
testcase_14 | AC | 363 ms
35,072 KB |
testcase_15 | AC | 16 ms
6,944 KB |
testcase_16 | AC | 282 ms
27,520 KB |
testcase_17 | AC | 458 ms
41,728 KB |
testcase_18 | AC | 57 ms
9,216 KB |
testcase_19 | AC | 313 ms
28,288 KB |
testcase_20 | AC | 533 ms
53,504 KB |
testcase_21 | AC | 60 ms
9,728 KB |
testcase_22 | AC | 869 ms
74,752 KB |
testcase_23 | AC | 170 ms
19,584 KB |
testcase_24 | AC | 77 ms
11,264 KB |
testcase_25 | AC | 4 ms
6,944 KB |
testcase_26 | AC | 683 ms
63,104 KB |
testcase_27 | AC | 852 ms
77,056 KB |
testcase_28 | AC | 534 ms
44,928 KB |
testcase_29 | AC | 128 ms
16,000 KB |
testcase_30 | AC | 267 ms
28,800 KB |
testcase_31 | AC | 152 ms
17,024 KB |
testcase_32 | AC | 1,039 ms
86,912 KB |
testcase_33 | AC | 2 ms
6,940 KB |
testcase_34 | AC | 2 ms
6,944 KB |
testcase_35 | AC | 2 ms
6,944 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; }