結果
問題 | No.2946 Puyo |
ユーザー | sorachandu |
提出日時 | 2024-10-25 21:37:42 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 5,392 bytes |
コンパイル時間 | 3,004 ms |
コンパイル使用メモリ | 256,372 KB |
実行使用メモリ | 24,960 KB |
最終ジャッジ日時 | 2024-10-25 21:37:50 |
合計ジャッジ時間 | 6,454 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 29 ms
8,320 KB |
testcase_04 | AC | 29 ms
8,320 KB |
testcase_05 | AC | 30 ms
8,320 KB |
testcase_06 | AC | 29 ms
8,320 KB |
testcase_07 | AC | 30 ms
8,320 KB |
testcase_08 | AC | 4 ms
6,820 KB |
testcase_09 | AC | 11 ms
6,820 KB |
testcase_10 | AC | 4 ms
6,820 KB |
testcase_11 | AC | 15 ms
6,820 KB |
testcase_12 | AC | 4 ms
6,820 KB |
testcase_13 | AC | 2 ms
6,820 KB |
testcase_14 | AC | 6 ms
6,820 KB |
testcase_15 | AC | 4 ms
6,816 KB |
testcase_16 | AC | 8 ms
6,820 KB |
testcase_17 | AC | 25 ms
6,820 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 15 ms
6,816 KB |
testcase_20 | AC | 18 ms
6,820 KB |
testcase_21 | AC | 31 ms
6,820 KB |
testcase_22 | AC | 6 ms
6,820 KB |
testcase_23 | AC | 23 ms
6,824 KB |
testcase_24 | AC | 49 ms
6,816 KB |
testcase_25 | AC | 43 ms
6,820 KB |
testcase_26 | AC | 48 ms
6,816 KB |
testcase_27 | AC | 3 ms
6,820 KB |
testcase_28 | AC | 34 ms
12,672 KB |
testcase_29 | AC | 46 ms
12,288 KB |
testcase_30 | AC | 27 ms
9,984 KB |
testcase_31 | AC | 39 ms
12,032 KB |
testcase_32 | AC | 35 ms
7,936 KB |
testcase_33 | AC | 30 ms
6,816 KB |
testcase_34 | AC | 43 ms
8,576 KB |
testcase_35 | AC | 34 ms
6,816 KB |
testcase_36 | AC | 33 ms
7,424 KB |
testcase_37 | AC | 34 ms
6,940 KB |
testcase_38 | AC | 22 ms
6,824 KB |
testcase_39 | AC | 20 ms
6,816 KB |
testcase_40 | AC | 13 ms
6,816 KB |
testcase_41 | AC | 25 ms
6,820 KB |
testcase_42 | AC | 22 ms
6,820 KB |
testcase_43 | AC | 42 ms
20,992 KB |
testcase_44 | AC | 52 ms
24,960 KB |
testcase_45 | AC | 38 ms
15,488 KB |
testcase_46 | AC | 20 ms
7,168 KB |
testcase_47 | AC | 30 ms
9,600 KB |
ソースコード
#if !__INCLUDE_LEVEL__ #include __FILE__ int main(){ int h,w; cin>>h>>w; vector<string> g(h); rep(i,0,h)cin>>g[i]; // 場外判定 auto outof = [&](ull y, ull x){ return (y >= h || x >= w); }; // 4方向の近傍 右,下,左,上 const int dy[4] = {0, 1, 0, -1}; const int dx[4] = {1, 0, -1, 0}; vector seen(h,vector<int>(w,0)); auto dfs=[&](auto self,int y,int x) -> int { int cnt=1; rep(i,0,4){ uint Y=y+dy[i],X=x+dx[i]; if(outof(Y,X) or g[y][x]!=g[Y][X] or seen[Y][X]) continue; seen[Y][X]=true; cnt+=self(self,Y,X); } return cnt; }; auto upd=[&](auto self,int y,int x) -> void { rep(i,0,4){ uint Y=y+dy[i],X=x+dx[i]; if(outof(Y,X) or g[y][x]!=g[Y][X] or seen[Y][X]==-1) continue; seen[Y][X]=-1; self(self,Y,X); } }; rep(i,0,h) rep(j,0,w){ if(!seen[i][j]){ seen[i][j]=true; if(dfs(dfs,i,j)>=4){ seen[i][j]=-1; upd(upd,i,j); } } } rep(i,0,h) rep(j,0,w){ if(seen[i][j]==-1) g[i][j]='.'; } rep(i,0,h) cout<<g[i]<<el; } #else #include <bits/stdc++.h> using namespace std; struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(13); } }init; using ll = long long; using ull = unsigned long long; using pii = pair<int,int>; using pll = pair<ll,ll>; #define rep(i, x, limit) for (ll i = (ll)x; i < (ll)limit; i++) #define REP(i, x, limit) for (ll i = (ll)x; i <= (ll)limit; i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define el '\n' #define spa ' ' #define Yes cout << "Yes" << el #define No cout << "No" << el #define YES cout << "YES" << el #define NO cout << "NO" << el #define eps (1e-10) #define Equals(a,b) (fabs((a) - (b)) < eps ) #define debug(x) cerr << #x << " = " << x << el const double pi = 3.141592653589793238; const int inf = 1073741823; const ll infl = 1LL << 60; const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string abc = "abcdefghijklmnopqrstuvwxyz"; template<typename T1, typename T2> std::ostream &operator<< (std::ostream &os, std::pair<T1,T2> p){ os << "{" << p.first << "," << p.second << "}"; return os; } // 配列の要素を空白区切りで出力 第二引数をtrueにすると改行区切り template<typename T> inline void print_vec(const vector<T> &v, bool split_line=false) { if(v.empty()){ cout << "This vector is empty." << el; return; } constexpr bool isValue = is_integral<T>::value; for (int i = 0; i < (int)v.size(); i++) { if constexpr(isValue){ if((v[i]==inf) || (v[i]==infl)) cout << 'x' << " \n"[split_line || i+1==(int)v.size()]; else cout << v[i] << " \n"[split_line || i+1==(int)v.size()]; }else cout << v[i] << " \n"[split_line || i+1==(int)v.size()]; } } template<typename T1, typename T2> inline void print_vec(const vector<pair<T1,T2>> &v, bool split_line=false){ if(v.empty()){ cout << "This vector is empty." << el; return; } for(int i = 0; i < (int)v.size(); i++){ cout << '{'; auto [a,b] = v[i]; constexpr pair<bool,bool> isValue = {is_integral<T1>::value, is_integral<T2>::value}; if constexpr(isValue.first){ if(a==inf || a==infl) cout << "x,"; else cout << a << ","; }else cout << a << ","; if constexpr(isValue.second){ if(b==inf || b==infl) cout << "x,"; else cout << b; }else cout << b; cout << "}" << " \n"[split_line || i+1==(int)v.size()]; } } template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { bool compare = a < b; if(compare) a = b; return compare; } template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { bool compare = a > b; if(compare) a = b; return compare; } // std::chronoを利用した時間計測用クラス class Timer{ chrono::system_clock::time_point start; public: Timer() : start(chrono::system_clock::now()) {} double count(){ chrono::duration<double> Time_ = chrono::system_clock::now() - start; return Time_.count(); } bool is_under(double x){ return (this -> count()) < x; } }; // std::uniform_int_distributionを利用した一様乱数生成クラス class Random_Gen{ random_device seed_gen; mt19937 engine; uniform_int_distribution<int64_t> dist; public: // Constructor [l,r]で生成する値の範囲を指定 Random_Gen() : engine(seed_gen()) {} Random_Gen(int64_t l, int64_t r) : engine(seed_gen()), dist(l,r) {} // 現在の生成する値の範囲をstd::pairで返す pair<int64_t,int64_t> get_range(){ return make_pair(dist.min(),dist.max()); } // 生成する値の範囲を[l,r]に変更する void set_range(int64_t l, int64_t r){ uniform_int_distribution<int64_t>::param_type Param(l,r); dist.param(Param); } // [l,r]内の一様分布の整数を返す int64_t gen(){ return dist(engine); } int64_t operator()(){ return gen(); } }; #endif