AtCoder Beginner Contest 164 F - I hate Matrix Construction

ビットごとに独立

ビットごとの論理和・論理積について考えているため、ビットごとに独立に考えることができる。したがって要素が0か1の $N \times N$ の行列を構築できるか？の問題に帰着できた。

容易に決定できる要素

まず、0か1か確定させられる要素を決めてしまおう。

論理積が1の行/列：全て1
論理和が0の行/列：全て0
$s_y=t_x$ であるような $(y,x)$ ： $s_y$

残りの要素

残りの決まっていない要素は「論理積が0」と「論理和が1」の制約からなる要素だけである。

試しにこれらの要素を全て0としてみる。このとき「論理積が0」という制約に反することはない。「論理和が1」が満たされない場合の対処を考える。そのような行(列)が存在する場合、「論理積が0」である列(行)のいずれかの要素を1にする必要がある。「論理積が0」である列(行)の要素を1にしたときに、その列(行)の要素が全て1にならないのであれば、1にしても問題がない。この条件を満たす列(行)を探し、1に変更する処理を「論理和が1」が満たされない全ての行(列)に対して行う。

行列の存在性

この処理を行った結果の行列が制約を満たさないならば、答えは-1である。結果が条件を満たさない場合、矛盾するパターンは2通り存在する。いずれの場合でも行列が存在することはありえない。

「容易に決定できる要素」の分で矛盾
「論理積が1」から1にしたいが「論理和が0」から0にする必要があるので不可能である。

	or 0	or 0
and 1	無理	無理

「残りの要素」の分で矛盾
0→1に変更する要素が足りないので「論理和が1」の制約を修正することは不可能である。

実装に関して

$a_{i,j} \lt 2^{64}$ より要素はunsigned long long intで管理する必要がある。また1<<iではなく1ULL<<iとしなければいけない。

#include <bits/stdc++.h>  
using namespace std;  
using ll = unsigned long long int;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1ULL<<60;  
  
int main() {  
    ll n;  
    cin >> n;  
    // 0 → and, 1 → or  
    vector<ll> s(n), t(n), u(n), v(n);  
    REP(i, n) cin >> s[i];  
    REP(i, n) cin >> t[i];  
    REP(i, n) cin >> u[i];  
    REP(i, n) cin >> v[i];  
  
    vector<vector<ll>> ans(n, vector<ll>(n));  
    REP(i, 64) {  
        // u2[j] = u[j]のiビット目  
        vector<ll> u2(n), v2(n);  
        REP(j, n) u2[j] = !!(u[j]&1ULL<<i), v2[j] = !!(v[j]&1ULL<<i);  
          
        // 確定させられる要素の分を決定  
        vector<vector<ll>> used(n, vector<ll>(n));  
        REP(j, n) if(s[j]==0 && u2[j]==1) REP(k, n) used[j][k] = 1;  
        REP(j, n) if(t[j]==0 && v2[j]==1) REP(k, n) used[k][j] = 1;  
        REP(j, n) REP(k, n) if(u2[j] == v2[k]) used[j][k] = u2[j];  
  
        // 論理和が1の行の制約を満たせるように  
        {  
            vector<ll> zeros(n);  
            REP(j, n) REP(k, n) zeros[k] += (used[j][k]==0);  
            REP(j, n) if(s[j]==1 && u2[j]==1) {  
                bool exist = false;  
                REP(k, n) if(used[j][k]==1) exist = true;  
                if(exist) continue;  
                // 制約違反の行がある  
                //「論理積が0」で1に変更しても0が残っている列を探す  
                REP(k, n) if(t[k]==0 && v2[k]==0 && zeros[k]>=2) {  
                    zeros[k]--;  
                    used[j][k] = 1;  
                    break;  
                }  
            }  
        }  
        // 論理和が1の列の制約を満たすように  
        {  
            vector<ll> zeros(n);  
            REP(j, n) REP(k, n) zeros[j] += (used[j][k]==0);  
            REP(j, n) if(t[j]==1 && v2[j]==1) {  
                bool exist = false;  
                REP(k, n) if(used[k][j]==1) exist = true;  
                if(exist) continue;  
                REP(k, n) if(s[k]==0 && u2[k]==0 && zeros[k]>=2) {  
                    zeros[k]--;  
                    used[k][j] = 1;  
                    break;  
                }  
            }  
        }  
          
        REP(j, n) REP(k, n) ans[j][k] |= used[j][k]<<i;  
    }  
  
    // 実際に構成した行列が制約を満たすか確認  
    auto check = [&] {  
        REP(i, n) {   
            ll and1 = ans[i][0], or1 = 0, and2 = ans[0][i], or2 = 0;  
            REP(j, n) {  
                and1 &= ans[i][j];  
                or1  |= ans[i][j];  
                and2 &= ans[j][i];  
                or2  |= ans[j][i];  
            }  
            if(s[i]==0 && u[i]!=and1) return false;  
            if(s[i]==1 && u[i]!=or1) return false;  
            if(t[i]==0 && v[i]!=and2) return false;  
            if(t[i]==1 && v[i]!=or2) return false;  
        }  
        return true;  
    };  
    if(!check()) {  
        cout << -1 << endl;  
        return 0;  
    }  
  
    REP(i, n) REP(j, n) cout << ans[i][j] << (j==n-1?'\n':' ');  
  
    return 0;  
}