ИТМО_21-22_N4_OK_30min

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int, int>
#define pb(x) push_back(x)
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v) {
    for (auto x : v) cout << x << ' ';
    cout << "\n";
}

void cvl(vector <ll> &v) {
    for (auto x : v) cout << x << ' ';
    cout << "\n";
}


void cvv(vector <vector <int> > &v) {
    for (auto x : v) cv(x);
    cout << "\n";
}

void cvb(vector <bool> v) {
    for (bool x : v) cout << x << ' ';
    cout << "\n";
}

void cvs(vector <string>  v) {
    for (auto a : v) {
        cout << a << "\n";
    }
}

void cvp(vector <pii> a) {
    for (auto p : a) {
        cout << p.first << ' ' << p.second << "\n";
    }
    cout << "\n";
}

set < vector <vector <int> > > all;

vector <vector <int> > now(9, vector <int> (9, -1));

string to(int x) {
    string s = "";
    while (x > 0) {
        s += x % 2 + '0';
        x /= 2;
    }
    reverse(s.begin(), s.end());
    while (s.size() < 17) {
        s = '0' + s;
    }
    return s;
}

void gen(string s) {
    vector <vector <int> > one = now;
    int id = -1;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (one[i][j] == -1) {
                id++;
                one[i][j] = s[id] - '0';
            }
        }
    }
    all.insert(one);
}

//1-bl, 0-wh
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //left up
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            now[i][j] = 1;
        }
    }
    for (int x = 0; x < pow(2, 17); ++x) {
        string s = to(x);
        gen(s);
    }

    //left down
    now.assign(9, vector <int> (9, -1));
    //cvv(now);
    for (int i = 1; i < 9; ++i) {
        for (int j = 0; j < 8; ++j) {
            now[i][j] = 1;
        }
    }
    for (int x = 0; x < pow(2, 17); ++x) {
        string s = to(x);
        gen(s);
    }

    //right up
    now.assign(9, vector <int> (9, -1));
    //cvv(now);
    for (int i = 0; i < 8; ++i) {
        for (int j = 1; j < 9; ++j) {
            now[i][j] = 1;
        }
    }
    for (int x = 0; x < pow(2, 17); ++x) {
        string s = to(x);
        gen(s);
    }

    //right down
    now.assign(9, vector <int> (9, -1));
    //cvv(now);
    for (int i = 1; i < 9; ++i) {
        for (int j = 1; j < 9; ++j) {
            now[i][j] = 1;
        }
    }
    for (int x = 0; x < pow(2, 17); ++x) {
        string s = to(x);
        gen(s);
    }
    cout << "all size = " << all.size() << "\n";
    int sz = all.size();
    int bit = sz * 81;
    cout << "bit = " << bit;
    int div = pow(2, 20) * 8;
    int ans = (bit + div - 1) / div;
    cout << "ans = " << ans << "\n";
}
/*
all size = 522239
bit = 42301359
ans = 6
*/