Submission #423613
Source Code Expand
#include <iostream> #include <cstdio> #include <cassert> #include <cstring> #include <vector> #include <valarray> #include <array> #include <queue> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <algorithm> #include <cmath> #include <complex> #include <random> #include <bitset> using namespace std; typedef long long ll; typedef pair<int, int> P; const int MN = 16; const int MB = 200; int Y, X; bool g[MN][MN]; typedef bitset<256> B; int main() { cin >> Y >> X; B b; bool f = false; for (int i = 0; i < Y; i++) { string s; cin >> s; for (int j = 0; j < X; j++) { b[i*MN+j] = (s[j] == '#'); if (s[j] == '.') f = true; } } if (!f) { cout << -1 << endl; return 0; } vector<B> v, v2; v.push_back(b); for (int t = 0; t <= MN; t++) { v2.clear(); for (B b: v) { if (b.count() == 0) { cout << t << endl; return 0; } for (int i = 0; i < Y; i++) { for (int j = 0; j < X; j++) { if (!b[i*MN+j]) { B bb = b; for (int u = 0; u < MN; u++) { bb[i*MN+u] = false; } for (int u = 0; u < MN; u++) { bb[u*MN+j] = false; } v2.push_back(bb); } } } } sort(v2.begin(), v2.end(), [&](const B &l, const B &r){ return l.count() < r.count(); }); v2.erase(unique(v2.begin(), v2.end()), v2.end()); if (v2.size() > MB) v2.resize(MB); v = v2; } assert(false); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 大爆発 |
User | yosupo |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 1946 Byte |
Status | AC |
Exec Time | 1240 ms |
Memory | 3092 KB |
Judge Result
Set Name | small | large | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
small | small/00_border_small_01.txt, small/00_border_small_02.txt, small/00_min_small_01.txt, small/00_min_small_02.txt, small/01_rand_small_00.txt, small/01_rand_small_01.txt, small/01_rand_small_02.txt, small/01_rand_small_03.txt, small/01_rand_small_04.txt, small/01_rand_small_05.txt, small/01_rand_small_06.txt, small/01_rand_small_07.txt, small/01_rand_small_08.txt, small/01_rand_small_09.txt, small/02_maxrand_small_00.txt, small/02_maxrand_small_01.txt, small/02_maxrand_small_02.txt, small/02_maxrand_small_03.txt, small/02_maxrand_small_04.txt, small/02_maxrand_small_05.txt, small/02_maxrand_small_06.txt, small/02_maxrand_small_07.txt, small/02_maxrand_small_08.txt, small/02_maxrand_small_09.txt, small/03_randhard_small_00.txt, small/03_randhard_small_01.txt, small/03_randhard_small_02.txt, small/03_randhard_small_03.txt, small/03_randhard_small_04.txt, small/03_randhard_small_05.txt, small/03_randhard_small_06.txt, small/03_randhard_small_07.txt, small/03_randhard_small_08.txt, small/03_randhard_small_09.txt, small/03_randhard_small_10.txt, small/03_randhard_small_11.txt, small/03_randhard_small_12.txt, small/03_randhard_small_13.txt, small/03_randhard_small_14.txt, small/03_randhard_small_15.txt, small/03_randhard_small_16.txt, small/03_randhard_small_17.txt, small/03_randhard_small_18.txt, small/03_randhard_small_19.txt, small/04_black_small_00.txt, small/04_black_small_01.txt, small/04_black_small_02.txt, small/04_black_small_03.txt, small/04_black_small_04.txt, small/0_sample1.txt, small/0_sample2.txt, small/0_sample4.txt |
large | small/00_border_small_01.txt, small/00_border_small_02.txt, small/00_min_small_01.txt, small/00_min_small_02.txt, small/01_rand_small_00.txt, small/01_rand_small_01.txt, small/01_rand_small_02.txt, small/01_rand_small_03.txt, small/01_rand_small_04.txt, small/01_rand_small_05.txt, small/01_rand_small_06.txt, small/01_rand_small_07.txt, small/01_rand_small_08.txt, small/01_rand_small_09.txt, small/02_maxrand_small_00.txt, small/02_maxrand_small_01.txt, small/02_maxrand_small_02.txt, small/02_maxrand_small_03.txt, small/02_maxrand_small_04.txt, small/02_maxrand_small_05.txt, small/02_maxrand_small_06.txt, small/02_maxrand_small_07.txt, small/02_maxrand_small_08.txt, small/02_maxrand_small_09.txt, small/03_randhard_small_00.txt, small/03_randhard_small_01.txt, small/03_randhard_small_02.txt, small/03_randhard_small_03.txt, small/03_randhard_small_04.txt, small/03_randhard_small_05.txt, small/03_randhard_small_06.txt, small/03_randhard_small_07.txt, small/03_randhard_small_08.txt, small/03_randhard_small_09.txt, small/03_randhard_small_10.txt, small/03_randhard_small_11.txt, small/03_randhard_small_12.txt, small/03_randhard_small_13.txt, small/03_randhard_small_14.txt, small/03_randhard_small_15.txt, small/03_randhard_small_16.txt, small/03_randhard_small_17.txt, small/03_randhard_small_18.txt, small/03_randhard_small_19.txt, small/04_black_small_00.txt, small/04_black_small_01.txt, small/04_black_small_02.txt, small/04_black_small_03.txt, small/04_black_small_04.txt, small/0_sample1.txt, small/0_sample2.txt, small/0_sample4.txt, large/00_border_large_01.txt, large/00_border_large_02.txt, large/00_doubleslash_large_00.txt, large/00_slash_large_00.txt, large/00_tripleslash_large_00.txt, large/01_rand_large_00.txt, large/01_rand_large_01.txt, large/01_rand_large_02.txt, large/01_rand_large_03.txt, large/01_rand_large_04.txt, large/01_rand_large_05.txt, large/01_rand_large_06.txt, large/01_rand_large_07.txt, large/01_rand_large_08.txt, large/01_rand_large_09.txt, large/02_maxrand_large_00.txt, large/02_maxrand_large_01.txt, large/02_maxrand_large_02.txt, large/02_maxrand_large_03.txt, large/02_maxrand_large_04.txt, large/02_maxrand_large_05.txt, large/02_maxrand_large_06.txt, large/02_maxrand_large_07.txt, large/02_maxrand_large_08.txt, large/02_maxrand_large_09.txt, large/03_randhard_large_00.txt, large/03_randhard_large_01.txt, large/03_randhard_large_02.txt, large/03_randhard_large_03.txt, large/03_randhard_large_04.txt, large/03_randhard_large_05.txt, large/03_randhard_large_06.txt, large/03_randhard_large_07.txt, large/03_randhard_large_08.txt, large/03_randhard_large_09.txt, large/03_randhard_large_10.txt, large/03_randhard_large_11.txt, large/03_randhard_large_12.txt, large/03_randhard_large_13.txt, large/03_randhard_large_14.txt, large/03_randhard_large_15.txt, large/03_randhard_large_16.txt, large/03_randhard_large_17.txt, large/03_randhard_large_18.txt, large/03_randhard_large_19.txt, large/04_black_large_00.txt, large/04_black_large_01.txt, large/04_black_large_02.txt, large/04_black_large_03.txt, large/04_black_large_04.txt, large/05_almostblack_large_00.txt, large/05_almostblack_large_01.txt, large/05_almostblack_large_02.txt, large/05_almostblack_large_03.txt, large/05_almostblack_large_04.txt, large/05_almostblack_large_05.txt, large/05_almostblack_large_06.txt, large/05_almostblack_large_07.txt, large/05_almostblack_large_08.txt, large/05_almostblack_large_09.txt, large/05_almostblack_large_10.txt, large/05_almostblack_large_11.txt, large/05_almostblack_large_12.txt, large/05_almostblack_large_13.txt, large/05_almostblack_large_14.txt, large/05_almostblack_large_15.txt, large/05_almostblack_large_16.txt, large/05_almostblack_large_17.txt, large/05_almostblack_large_18.txt, large/05_almostblack_large_19.txt, large/0_sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/00_border_large_01.txt | AC | 456 ms | 3004 KB |
large/00_border_large_02.txt | AC | 492 ms | 3004 KB |
large/00_doubleslash_large_00.txt | AC | 769 ms | 3000 KB |
large/00_slash_large_00.txt | AC | 772 ms | 3004 KB |
large/00_tripleslash_large_00.txt | AC | 955 ms | 2920 KB |
large/01_rand_large_00.txt | AC | 25 ms | 928 KB |
large/01_rand_large_01.txt | AC | 25 ms | 924 KB |
large/01_rand_large_02.txt | AC | 25 ms | 924 KB |
large/01_rand_large_03.txt | AC | 177 ms | 1980 KB |
large/01_rand_large_04.txt | AC | 869 ms | 2968 KB |
large/01_rand_large_05.txt | AC | 41 ms | 1308 KB |
large/01_rand_large_06.txt | AC | 376 ms | 1948 KB |
large/01_rand_large_07.txt | AC | 25 ms | 920 KB |
large/01_rand_large_08.txt | AC | 156 ms | 1980 KB |
large/01_rand_large_09.txt | AC | 26 ms | 796 KB |
large/02_maxrand_large_00.txt | AC | 27 ms | 916 KB |
large/02_maxrand_large_01.txt | AC | 461 ms | 3000 KB |
large/02_maxrand_large_02.txt | AC | 855 ms | 2960 KB |
large/02_maxrand_large_03.txt | AC | 969 ms | 3000 KB |
large/02_maxrand_large_04.txt | AC | 993 ms | 3000 KB |
large/02_maxrand_large_05.txt | AC | 1048 ms | 3092 KB |
large/02_maxrand_large_06.txt | AC | 1122 ms | 3000 KB |
large/02_maxrand_large_07.txt | AC | 1107 ms | 2908 KB |
large/02_maxrand_large_08.txt | AC | 1206 ms | 3000 KB |
large/02_maxrand_large_09.txt | AC | 28 ms | 924 KB |
large/03_randhard_large_00.txt | AC | 26 ms | 920 KB |
large/03_randhard_large_01.txt | AC | 342 ms | 2996 KB |
large/03_randhard_large_02.txt | AC | 671 ms | 2996 KB |
large/03_randhard_large_03.txt | AC | 667 ms | 3004 KB |
large/03_randhard_large_04.txt | AC | 759 ms | 3088 KB |
large/03_randhard_large_05.txt | AC | 549 ms | 2912 KB |
large/03_randhard_large_06.txt | AC | 457 ms | 2912 KB |
large/03_randhard_large_07.txt | AC | 1003 ms | 2956 KB |
large/03_randhard_large_08.txt | AC | 978 ms | 3000 KB |
large/03_randhard_large_09.txt | AC | 714 ms | 2956 KB |
large/03_randhard_large_10.txt | AC | 980 ms | 2956 KB |
large/03_randhard_large_11.txt | AC | 494 ms | 3000 KB |
large/03_randhard_large_12.txt | AC | 1080 ms | 3004 KB |
large/03_randhard_large_13.txt | AC | 622 ms | 3000 KB |
large/03_randhard_large_14.txt | AC | 874 ms | 3000 KB |
large/03_randhard_large_15.txt | AC | 586 ms | 3000 KB |
large/03_randhard_large_16.txt | AC | 1240 ms | 2908 KB |
large/03_randhard_large_17.txt | AC | 639 ms | 3004 KB |
large/03_randhard_large_18.txt | AC | 531 ms | 2900 KB |
large/03_randhard_large_19.txt | AC | 886 ms | 3000 KB |
large/04_black_large_00.txt | AC | 26 ms | 804 KB |
large/04_black_large_01.txt | AC | 788 ms | 3000 KB |
large/04_black_large_02.txt | AC | 1088 ms | 2960 KB |
large/04_black_large_03.txt | AC | 25 ms | 920 KB |
large/04_black_large_04.txt | AC | 1009 ms | 3016 KB |
large/05_almostblack_large_00.txt | AC | 467 ms | 1984 KB |
large/05_almostblack_large_01.txt | AC | 436 ms | 1980 KB |
large/05_almostblack_large_02.txt | AC | 504 ms | 2960 KB |
large/05_almostblack_large_03.txt | AC | 182 ms | 1936 KB |
large/05_almostblack_large_04.txt | AC | 424 ms | 1872 KB |
large/05_almostblack_large_05.txt | AC | 764 ms | 2952 KB |
large/05_almostblack_large_06.txt | AC | 487 ms | 3000 KB |
large/05_almostblack_large_07.txt | AC | 656 ms | 3000 KB |
large/05_almostblack_large_08.txt | AC | 26 ms | 908 KB |
large/05_almostblack_large_09.txt | AC | 524 ms | 2060 KB |
large/05_almostblack_large_10.txt | AC | 103 ms | 1980 KB |
large/05_almostblack_large_11.txt | AC | 766 ms | 2896 KB |
large/05_almostblack_large_12.txt | AC | 676 ms | 3000 KB |
large/05_almostblack_large_13.txt | AC | 490 ms | 3028 KB |
large/05_almostblack_large_14.txt | AC | 385 ms | 1976 KB |
large/05_almostblack_large_15.txt | AC | 276 ms | 1876 KB |
large/05_almostblack_large_16.txt | AC | 615 ms | 3084 KB |
large/05_almostblack_large_17.txt | AC | 406 ms | 1980 KB |
large/05_almostblack_large_18.txt | AC | 361 ms | 1896 KB |
large/05_almostblack_large_19.txt | AC | 531 ms | 3000 KB |
large/0_sample3.txt | AC | 26 ms | 752 KB |
small/00_border_small_01.txt | AC | 33 ms | 1056 KB |
small/00_border_small_02.txt | AC | 26 ms | 924 KB |
small/00_min_small_01.txt | AC | 26 ms | 924 KB |
small/00_min_small_02.txt | AC | 27 ms | 888 KB |
small/01_rand_small_00.txt | AC | 25 ms | 928 KB |
small/01_rand_small_01.txt | AC | 25 ms | 928 KB |
small/01_rand_small_02.txt | AC | 25 ms | 928 KB |
small/01_rand_small_03.txt | AC | 29 ms | 1052 KB |
small/01_rand_small_04.txt | AC | 26 ms | 920 KB |
small/01_rand_small_05.txt | AC | 24 ms | 928 KB |
small/01_rand_small_06.txt | AC | 25 ms | 800 KB |
small/01_rand_small_07.txt | AC | 26 ms | 924 KB |
small/01_rand_small_08.txt | AC | 26 ms | 924 KB |
small/01_rand_small_09.txt | AC | 26 ms | 792 KB |
small/02_maxrand_small_00.txt | AC | 27 ms | 920 KB |
small/02_maxrand_small_01.txt | AC | 27 ms | 920 KB |
small/02_maxrand_small_02.txt | AC | 26 ms | 916 KB |
small/02_maxrand_small_03.txt | AC | 30 ms | 860 KB |
small/02_maxrand_small_04.txt | AC | 37 ms | 1220 KB |
small/02_maxrand_small_05.txt | AC | 31 ms | 1188 KB |
small/02_maxrand_small_06.txt | AC | 45 ms | 1136 KB |
small/02_maxrand_small_07.txt | AC | 36 ms | 1192 KB |
small/02_maxrand_small_08.txt | AC | 39 ms | 1224 KB |
small/02_maxrand_small_09.txt | AC | 25 ms | 800 KB |
small/03_randhard_small_00.txt | AC | 26 ms | 792 KB |
small/03_randhard_small_01.txt | AC | 28 ms | 936 KB |
small/03_randhard_small_02.txt | AC | 28 ms | 932 KB |
small/03_randhard_small_03.txt | AC | 31 ms | 800 KB |
small/03_randhard_small_04.txt | AC | 28 ms | 796 KB |
small/03_randhard_small_05.txt | AC | 28 ms | 804 KB |
small/03_randhard_small_06.txt | AC | 27 ms | 800 KB |
small/03_randhard_small_07.txt | AC | 28 ms | 924 KB |
small/03_randhard_small_08.txt | AC | 33 ms | 1064 KB |
small/03_randhard_small_09.txt | AC | 31 ms | 968 KB |
small/03_randhard_small_10.txt | AC | 33 ms | 1092 KB |
small/03_randhard_small_11.txt | AC | 26 ms | 804 KB |
small/03_randhard_small_12.txt | AC | 38 ms | 1184 KB |
small/03_randhard_small_13.txt | AC | 37 ms | 1184 KB |
small/03_randhard_small_14.txt | AC | 38 ms | 1224 KB |
small/03_randhard_small_15.txt | AC | 41 ms | 1224 KB |
small/03_randhard_small_16.txt | AC | 44 ms | 1224 KB |
small/03_randhard_small_17.txt | AC | 26 ms | 928 KB |
small/03_randhard_small_18.txt | AC | 40 ms | 1192 KB |
small/03_randhard_small_19.txt | AC | 39 ms | 1056 KB |
small/04_black_small_00.txt | AC | 24 ms | 672 KB |
small/04_black_small_01.txt | AC | 40 ms | 1220 KB |
small/04_black_small_02.txt | AC | 42 ms | 1216 KB |
small/04_black_small_03.txt | AC | 39 ms | 1196 KB |
small/04_black_small_04.txt | AC | 34 ms | 968 KB |
small/0_sample1.txt | AC | 25 ms | 932 KB |
small/0_sample2.txt | AC | 33 ms | 1012 KB |
small/0_sample4.txt | AC | 25 ms | 924 KB |