1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <bitset>
#include <unordered_set>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < n; ++i)

class Shutter {
    static constexpr int N = 100;
    using Config = bitset<N * N>;
    Config screen;
    unordered_set<size_t> seen_configs;

    int idx(int i, int j) { return i * N + j; }
    static size_t config_hash(const Config &config) { return hash<string>()(config.to_string()); }

public:
    Shutter() {
        REP(i, N)
            REP(j, N)
                screen[idx(i, j)] = ((i + j) % 2 == 0 ? 1 : 0);

        screen[idx(1, 1)] = !screen[idx(1, 1)];
        screen[idx(2, 2)] = !screen[idx(2, 2)];
        screen[idx(3, 3)] = !screen[idx(3, 3)];
        screen[idx(4, 4)] = !screen[idx(4, 4)];
    }

    void resolve() {
        seen_configs.insert(config_hash(screen));
        while (true) {
            vector<pair<int, int> > to_flip;
            REP(i, N-1)
                REP(j, N-1) {
                    bool d1 = screen[idx(i, j)] && screen[idx(i + 1, j + 1)] && !screen[idx(i, j + 1)] && !screen[idx(
                                  i + 1, j)];
                    bool d2 = !screen[idx(i, j)] && !screen[idx(i + 1, j + 1)] && screen[idx(i, j + 1)] && screen[idx(
                                  i + 1, j)];
                    if (d1 || d2) {
                        to_flip.push_back({i, j});
                        to_flip.push_back({i + 1, j});
                        to_flip.push_back({i, j + 1});
                        to_flip.push_back({i + 1, j + 1});
                    }
                }
            for (auto [x, y]: to_flip)
                screen.flip(idx(x, y));
            size_t current_hash = config_hash(screen);
            if (seen_configs.count(current_hash))
                break;
            seen_configs.insert(current_hash);
        }
        REP(i, N) {
            REP(j, N)
                cout << screen[idx(i, j)];
            cout << endl;
        }
    }
};

int main() {
    Shutter simulator;
    simulator.resolve();
    return 0;
}