結果

問題 No.1421 国勢調査 (Hard)
コンテスト
ユーザー logx
提出日時 2021-01-29 21:31:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 123 ms / 2,000 ms
コード長 2,596 bytes
コンパイル時間 1,759 ms
コンパイル使用メモリ 175,528 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-27 07:39:19
合計ジャッジ時間 4,575 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long ll;


const int MAX_COL=51;//適宜.
struct bitMatrix{
    int h,w;
    vector<bitset<MAX_COL>> val;
    bitMatrix(int m=1,int n=1):h(m),w(n){
        val.resize(m);
    }
    inline bitset<MAX_COL>& operator[](const int i){return val[i];}
};

int bit_Gauss_Jordan(bitMatrix &a,bool is_ex=false){
    int rank=0;
    for(int col=0;col<a.w;col++){
        if(is_ex && col+1==a.w)break;
        //その列の非零元を探し,上へ.
        int piv=-1;
        for(int row=rank;row<a.h;row++){
            if(a[row][col]){
                piv=row;
                break;
            }
        }
        if(piv==-1)continue;
        swap(a[piv] , a[rank]);
        //F_2で非零元は1なので,ピボットは必ず1.

        //その列に零でない元があると困るので,それを取り除く.
        //xorが足し算/引き算に相当する.
        for(int row=0;row<a.h;row++){
            if(row!=rank && a[row][col])a[row]^=a[rank];
        }
        rank++;
    }
    return rank;
}

int bit_linear_equation(bitMatrix A,vector<int> b,vector<int> &res){
    int m=A.h;
    int n=A.w;
    bitMatrix M(m,n+1);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            M[i][j]=A[i][j];
        }
        M[i][n]=b[i];
    }
    int rank=bit_Gauss_Jordan(M,true);
    for(int row=rank;row<m;row++)if(M[row][n])return -1;
    res.assign(n,0);
    for(int i=0;i<rank;i++){
        int idx=0;
        for(int j=0;;j++)if(M[i][j]){idx=j;break;}
        res[idx]=M[i][n];
    }
    return rank;
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N,M;cin >> N >> M;
    assert(1<=N<=50);
    assert(1<=M<=10000);
    bitMatrix B(M,N);
    vector<int> Y(M);
    for(int i=0;i<M;i++){
        int A;cin >> A;
        assert(1<=A<=N);
        int last=-1;
        for(int j=0;j<A;j++){
            int b;cin >> b;
            assert(1<=b<=N);
            assert(last<b);
            last=b;
            B[i][b-1]=1;
        }
        cin >> Y[i];
        assert(0<=Y[i]<(1<<30));
    }

    bool ok=true;
    vector<int> ans(N);
    vector<int> res;
    vector<int> b(M);
    for(int i=0;i<30;i++){
        for(int j=0;j<M;j++)b[j]=((Y[j]>>i)&1);
        int rank=bit_linear_equation(B,b,res);
        if(rank==-1){
            ok=false;
            break;
        }
        for(int j=0;j<N;j++)ans[j]|=(1<<i)*res[j];
    }
    if(!ok)cout << -1 << endl;
    else{
        for(int i=0;i<N;i++)cout << ans[i] << endl;
    }
}
0