結果

問題 No.1421 国勢調査 (Hard)
ユーザー logxlogx
提出日時 2021-01-29 21:31:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 2,596 bytes
コンパイル時間 1,638 ms
コンパイル使用メモリ 174,784 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-09 14:46:45
合計ジャッジ時間 4,737 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 122 ms
4,376 KB
testcase_23 AC 121 ms
4,376 KB
testcase_24 AC 122 ms
4,376 KB
testcase_25 AC 121 ms
4,376 KB
testcase_26 AC 122 ms
4,376 KB
testcase_27 AC 23 ms
4,380 KB
testcase_28 AC 32 ms
4,376 KB
testcase_29 AC 26 ms
4,376 KB
testcase_30 AC 22 ms
4,380 KB
testcase_31 AC 26 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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