p307.ans1
======================
0110
1001
0110

=================
p307.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/graph/two_sat.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class TwoSat {
  private:
    vector<bool> visited;

    void dfs1(int u) {
        visited[u] = true;
        for(int v: adj[u]) {
            if(!visited[v]) {
                dfs1(v);
            }
        }

        top_sort.push_back(u);
    }

    void dfs2(int u) {
        for(int v: radj[u]) {
            if(comp[v] == -1) {
                comp[v] = comp[u];
                dfs2(v);
            }
        }
    }

  public:
    int n;
    vector<vector<int>> adj, radj;
    vector<int> comp, comp_ids, top_sort;

    TwoSat() {}
    TwoSat(int _n) { init(_n); }

    void init(int _n) {
        n = _n;
        comp_ids.clear();
        top_sort.clear();
        adj.assign(2 * n, {});
        radj.assign(2 * n, {});
    }

    void add_implication(int u, int v, bool neg_u = false, bool neg_v = false) {
        adj[u << 1 | neg_u].push_back(v << 1 | neg_v);
        radj[v << 1 | neg_v].push_back(u << 1 | neg_u);
    }

    pair<bool, vector<bool>> solve() {
        comp.assign(2 * n, -1);
        visited.assign(2 * n, false);

        for(int i = 0; i < 2 * n; i++) {
            if(!visited[i]) {
                dfs1(i);
            }
        }

        reverse(top_sort.begin(), top_sort.end());
        for(int u: top_sort) {
            if(comp[u] == -1) {
                comp[u] = (int)comp_ids.size();
                comp_ids.push_back(comp[u]);
                dfs2(u);
            }
        }

        vector<bool> assignment(n);
        for(int i = 0; i < n; i++) {
            if(comp[i << 1] == comp[i << 1 | 1]) {
                return {false, {}};
            }

            assignment[i] = comp[i << 1] > comp[i << 1 | 1];
        }

        return {true, assignment};
    }
};

int n, m;
vector<vector<int>> tbl;

void read() {
    cin >> n >> m;
    tbl.assign(n - 1, vector<int>(m - 1));
    for(int i = 0; i < n - 1; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < m - 1; j++) {
            tbl[i][j] = s[j] - '0';
        }
    }
}

void solve() {
    // Once we fix the whole first row and first column of the key A, every
    // remaining cell is forced: A[i][j] = B[i-1][j-1] - A[i-1][j] - A[i][j-1] -
    // A[i-1][j-1]. Writing A[i][0] and A[0][j] as unknown bits, the parity
    // structure makes each forced cell a linear expression in just A[0][0], one
    // row bit (row i) and one column bit (col j), with sign depending on the
    // parities of i and j. The validity constraint A[i][j] in {0, 1} becomes,
    // for each (i, j), a forbidden combination of (row bit, col bit), i.e. a
    // 2-SAT clause over n + m - 2 variables (the n - 1 row bits and m - 1 column
    // bits).
    //
    // We brute force the two choices of A[0][0]; for each we build the 2-SAT
    // instance, where any (value_row, value_col) pair that would push a cell
    // outside {0, 1} is forbidden via the implications "row bit = value_row ->
    // col bit != value_col" and its contrapositive. If the 2-SAT is satisfiable
    // we read off the first row/column from the assignment, fill the rest, and
    // print the key; otherwise the fingerprint is CORRUPT.

    for(int value00 = 0; value00 < 2; value00++) {
        vector<vector<int>> delta(n, vector<int>(m, 0));
        delta[0][0] = value00;

        TwoSat ts(n + m - 2);
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                delta[i][j] = tbl[i - 1][j - 1] - delta[i - 1][j] -
                              delta[i][j - 1] - delta[i - 1][j - 1];

                for(int value_row = 0; value_row < 2; value_row++) {
                    for(int value_col = 0; value_col < 2; value_col++) {
                        int real_delta = delta[i][j];
                        if(j % 2 == 0) {
                            real_delta += value_row;
                        } else {
                            real_delta -= value_row;
                        }
                        if(i % 2 == 0) {
                            real_delta += value_col;
                        } else {
                            real_delta -= value_col;
                        }

                        if(real_delta == 0 || real_delta == 1) {
                            continue;
                        }

                        int u = i - 1;
                        int v = j + n - 2;
                        ts.add_implication(
                            u, v, value_row == 0, value_col == 1
                        );

                        ts.add_implication(
                            v, u, value_col == 0, value_row == 1
                        );
                    }
                }
            }
        }

        auto [is_possible, assignment] = ts.solve();
        if(!is_possible) {
            continue;
        }

        vector<vector<int>> ans(n, vector<int>(m, 0));
        ans[0][0] = value00;
        for(int i = 1; i < n; i++) {
            ans[i][0] = assignment[i - 1];
        }

        for(int j = 1; j < m; j++) {
            ans[0][j] = assignment[n + j - 2];
        }

        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                ans[i][j] = tbl[i - 1][j - 1] - ans[i - 1][j] - ans[i][j - 1] -
                            ans[i - 1][j - 1];
                assert(ans[i][j] == 0 || ans[i][j] == 1);
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cout << ans[i][j];
            }
            cout << '\n';
        }

        return;
    }

    cout << "CORRUPT\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p307.in1
======================
3 4
222
222

=================
statement.txt
======================
307. Cipher
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



ASN has just invented a brand new cipher. Its key is just a H x W matrix of 0's and 1's. A tool by Macrosoft is recommended to be used as a manager of those keys. This tool stores a fingerprint for each key to protect from storage failures. Such a fingerprint is an (H-1) x (W-1) matrix consisting of 2 x 2 sums; i.e., if A is the key and B is the fingerprint, then Bij=Aij+Ai+1,j+Ai,j+1+Ai+1,j+1. Given the fingerprint, you are to find at least one key with such fingerprint, or to report that the fingerprint is corrupt (in case no key can produce it).

Input
The first line of the input file contains two numbers, H and W (2 ≤ H, W ≤ 300). The next H-1 lines contain W-1 characters each with no spaces in between, describing the fingerprint. Each of those characters will be either 0, 1, 2, 3, or 4.

Output
Output the key using the format similar to that of the input file: output H lines containing W characters (0 or 1) each, with no spaces in between.

If the fingerprint is corrupt, output CORRUPT on the only line of output.

Example(s)
sample input
sample output
3 4
222
222
0110
1001
0110

=================
