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
AC × 52
AC × 123
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