結果
問題 | No.2641 draw X |
ユーザー | kenken714 |
提出日時 | 2024-02-19 22:22:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 3,356 bytes |
コンパイル時間 | 2,424 ms |
コンパイル使用メモリ | 215,736 KB |
実行使用メモリ | 68,352 KB |
最終ジャッジ日時 | 2024-02-19 22:22:20 |
合計ジャッジ時間 | 6,029 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 1 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 2 ms
6,676 KB |
testcase_07 | AC | 2 ms
6,676 KB |
testcase_08 | AC | 2 ms
6,676 KB |
testcase_09 | AC | 2 ms
6,676 KB |
testcase_10 | AC | 2 ms
6,676 KB |
testcase_11 | AC | 2 ms
6,676 KB |
testcase_12 | AC | 2 ms
6,676 KB |
testcase_13 | AC | 2 ms
6,676 KB |
testcase_14 | AC | 2 ms
6,676 KB |
testcase_15 | AC | 136 ms
68,352 KB |
testcase_16 | AC | 139 ms
68,352 KB |
testcase_17 | AC | 2 ms
6,676 KB |
testcase_18 | AC | 2 ms
6,676 KB |
testcase_19 | AC | 2 ms
6,676 KB |
testcase_20 | AC | 9 ms
7,936 KB |
testcase_21 | AC | 19 ms
13,440 KB |
testcase_22 | AC | 9 ms
7,552 KB |
testcase_23 | AC | 17 ms
12,032 KB |
testcase_24 | AC | 7 ms
7,040 KB |
testcase_25 | AC | 5 ms
6,676 KB |
testcase_26 | AC | 21 ms
13,824 KB |
testcase_27 | AC | 5 ms
6,676 KB |
testcase_28 | AC | 36 ms
25,472 KB |
testcase_29 | AC | 96 ms
53,120 KB |
testcase_30 | AC | 82 ms
45,056 KB |
testcase_31 | AC | 54 ms
30,848 KB |
testcase_32 | AC | 146 ms
53,248 KB |
testcase_33 | AC | 89 ms
52,864 KB |
testcase_34 | AC | 47 ms
31,584 KB |
testcase_35 | AC | 48 ms
28,288 KB |
testcase_36 | AC | 127 ms
61,440 KB |
testcase_37 | AC | 126 ms
65,152 KB |
testcase_38 | AC | 111 ms
57,600 KB |
testcase_39 | AC | 138 ms
67,328 KB |
testcase_40 | AC | 132 ms
64,128 KB |
testcase_41 | AC | 122 ms
57,728 KB |
testcase_42 | AC | 119 ms
60,928 KB |
testcase_43 | AC | 128 ms
58,496 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #define REP(i, n) for(ll i = 0;i < n;i++) #define REPR(i, n) for(ll i = n;i >= 0;i--) #define FOR(i, m, n) for(ll i = m;i < n;i++) #define FORR(i, m, n) for(ll i = m;i >= n;i--) #define REPO(i, n) for(ll i = 1;i <= n;i++) #define ll long long #define INF (ll)1ll << 60 #define MINF (-1 * INF) #define ALL(n) n.begin(),n.end() #define MOD (ll)1000000007 #define P pair<ll, ll> ll h, w; vector<string> s; vector<vector<ll>> v[4], r[4]; bool check(ll x, ll y){ if(0 <= x and x < h and 0 <= y and y < w) return true; return false; } void solve(ll num, ll x0, ll y0, ll dx1, ll dy1, ll dx2, ll dy2, ll dx, ll dy){ ll x = x0, y = y0; while(1){ ll nx = x, ny = y, now = 0; while(1){ if(s[nx][ny] == '#'){ now++; } else now = 0; v[num][nx][ny] = now; if(!check(nx + dx, ny + dy))break; nx += dx; ny += dy; } if(!check(x + dx1, y + dy1))break; x += dx1; y += dy1; } x += dx2; y += dy2; if(!check(x + dx2, y + dy2))return; while(1){ ll nx = x, ny = y, now = 0; while(1){ if(s[nx][ny] == '#'){ now++; } else now = 0; v[num][nx][ny] = now; if(!check(nx + dx, ny + dy))break; nx += dx; ny += dy; } if(!check(x + dx2, y + dy2))break; x += dx2; y += dy2; } } void solve2(ll num, ll x0, ll y0, ll dx1, ll dy1, ll dx2, ll dy2, ll dx, ll dy){ ll x = x0, y = y0; while(1){ ll nx = x, ny = y, now = 0; while(1){ now = max(now - 1, r[num][nx][ny]); r[num][nx][ny] = now; if(!check(nx + dx, ny + dy))break; nx += dx; ny += dy; } if(!check(x + dx1, y + dy1))break; x += dx1; y += dy1; } x += dx2; y += dy2; if(!check(x + dx2, y + dy2))return; while(1){ ll nx = x, ny = y, now = 0; while(1){ now = max(now - 1, r[num][nx][ny]); r[num][nx][ny] = now; if(!check(nx + dx, ny + dy))break; nx += dx; ny += dy; } if(!check(x + dx2, y + dy2))break; x += dx2; y += dy2; } } int main(){ cin >> h >> w; s.resize(h); REP(i, 4) v[i].resize(h, vector<ll>(w)); REP(i, 4) r[i].resize(h, vector<ll>(w)); REP(i, h)cin >> s[i]; solve(0, 0, w - 1, 0, -1, 1, 0, 1, 1); solve(1, 0, 0, 0, 1, 1, 0, 1, -1); solve(2, h - 1, 0, 0, 1, -1, 0, -1, -1); solve(3, 0, 0, 1, 0, 0, 1, -1, 1); REP(i, h){ REP(j, w){ ll now = INF; REP(k, 4)now = min(now, v[k][i][j]); if(now >= 2){ REP(k, 4) r[k][i][j] = now; } } } solve2(0, 0, w - 1, 0, -1, 1, 0, 1, 1); solve2(1, 0, 0, 0, 1, 1, 0, 1, -1); solve2(2, h - 1, 0, 0, 1, -1, 0, -1, -1); solve2(3, 0, 0, 1, 0, 0, 1, -1, 1); REP(i, h){ REP(j, w){ ll now = 0; REP(k, 4)now = max(now, r[k][i][j]); if(now == 0 and s[i][j] == '#'){ cout <<"No" << endl; return 0; } } } cout <<"Yes"<<endl; }