結果

問題 No.1421 国勢調査 (Hard)
コンテスト
ユーザー logx
提出日時 2021-01-28 00:56:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 157 ms / 2,000 ms
コード長 6,900 bytes
コンパイル時間 1,804 ms
コンパイル使用メモリ 176,184 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-27 03:01:28
合計ジャッジ時間 4,368 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;

/*---------macro---------*/
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = s; i < (int)(n); ++i)
#define Clear(a) a = decltype(a)()
#define all(a) begin(a),end(a)
#define rall(a) rbegin(a),rend(a)
#define bit(i,j) ((i>>j)&1)

/*---------type/const---------*/
typedef long long ll;
typedef unsigned long long ull;
typedef string::const_iterator state; //構文解析
const ll big=1000000007;
//const ll big=998244353;
const double PI=acos(-1);
const double EPS=1e-8;//適宜変える
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const char newl='\n';
struct{
    constexpr operator int(){return int(1e9)+1;}
    constexpr operator ll(){return ll(1e18)+1;}
    constexpr auto operator-(){
        struct{
            constexpr operator int(){return -int(1e9)-1;}
            constexpr operator ll(){return -ll(1e18)-1;}
        }_ret;
        return _ret;
    }
}inf;

/*---------debug用関数---------*/
#ifdef LOGX
#define _GLIBCXX_DEBUG
#define dbg(x) cout << #x << ':',prt(x);
template<typename T> inline void prt(T a_);
template<typename T> inline void _prt(T a_);
template<typename A,typename B> inline void _prt(map<A,B> a_);
template<typename A,typename B> inline void _prt(unordered_map<A,B> a_);
template<typename T> inline void _prt(set<T> a_);
template<typename T> inline void _prt(unordered_set<T> a_);
template<typename A,typename B> inline void _prt(pair<A,B> a_);
template<typename T> inline void _prt(vector<T> &a_);
template<typename T> inline void _prt(vector<vector<T>> &a_);
//_prtでは改行しない.
inline void _prt(bool a_){if(a_)cout<<1;else cout<<0;}
inline void _prt(int a_){if(a_>=(int)inf)cout << "inf";else if(a_<=-(int)inf)cout << "-inf";else cout << a_;}
inline void _prt(long long a_){if(a_>=(ll)inf)cout << "INF";else if(a_<=-(ll)inf)cout << "-INF";else cout << a_;}
#ifdef ATCODER_MODINT_HPP
template<int MOD>inline void _prt(static_modint<MOD> x){cout << x.val();}
template<int MOD>inline void _prt(dynamic_modint<MOD> x){cout << x.val();}
#endif
template<typename T> inline void _prt(T a_){cout << a_;}
template<typename A,typename B>
inline void _prt(map<A,B> a_){cout<<'{';auto it=a_.begin();while(it!=a_.end()){_prt((*it).first);cout<<':';_prt((*(it++)).second);cout<<(it==a_.end() ? "":",");}cout<<'}';}
template<typename A,typename B>
inline void _prt(unordered_map<A,B> a_){cout<<'{';auto it=a_.begin();while(it!=a_.end()){_prt((*it).first);cout<<':';_prt((*(it++)).second);cout<<(it==a_.end() ? "":",");}cout<<'}';}
template<typename T>
inline void _prt(set<T> a_){cout<<'{';auto it=a_.begin();while(it!=a_.end()){_prt(*it++);cout<<(it==a_.end() ? "":",");}cout<<'}';}
template<typename T>
inline void _prt(unordered_set<T> a_){cout<<'{';auto it=a_.begin();while(it!=a_.end()){_prt(*it++);cout<<(it==a_.end() ? "":",");}cout<<'}';}
template<typename A,typename B>
inline void _prt(pair<A,B> a_){cout << '(';_prt(a_.first);cout << ',';_prt(a_.second);cout << ')';}
template<typename T>
inline void _prt(vector<T> &a_){cout<<'{';for(int i=0;i<(int)a_.size();i++){_prt(a_[i]);if(i+1<(int)a_.size())cout<<',';}cout<<'}';}
template<typename T>
inline void _prt(vector<vector<T>> &a_){cout<<"{\n";for(int i=0;i<(int)a_.size();i++){_prt(a_[i]);if(i+1<(int)a_.size())cout<<",\n";else cout<<"\n}";}}
template<typename T> inline void prt(T a_){_prt(a_);cout<<'\n';}
#else
#define dbg(x) ;
#define prt(x) ;
#define _prt(x) ;
#endif

/*---------function---------*/
template<typename T,typename U> T max(const T x,const U y){if(x>y)return x;else return y;}
template<typename T,typename U> T min(const T x,const U y){if(x<y)return x;else return y;}
template<typename T> T max(const vector<T> &a){T ans=a[0];for(T elem:a){ans=max(ans,elem);}return ans;}
template<typename T> T min(const vector<T> &a){T ans=a[0];for(T elem:a){ans=min(ans,elem);}return ans;}
template<typename T,typename U> bool chmin(T &a,const U b){if(a>b){a=b;return true;}return false;}
template<typename T,typename U> bool chmax(T &a,const U b){if(a<b){a=b;return true;}return false;}
template<typename T,typename U>
T expm(T x,U y,const ll mod=big){
    T res=1;
    while(y){
        if(y&1)(res*=x)%=mod;
        (x*=x)%=mod;
        y>>=1;
    }
    return res;
}
template<typename T,typename U>
T exp(T x,U y){
    T res=1;
    while(y){
        if(y&1)res*=x;
        x*=x;
        y>>=1;
    }
    return res;
}

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(){
    int N,M;cin >> N >> M;
    assert(1<=N && N<=50 && 1<=M && M<=100000);
    bitMatrix B(M,N);
    vector<int> Y(M);
    for(int i=0;i<M;i++){
        int A;cin >> A;
        assert(1<=A && A<=N);
        int last=-1;
        for(int j=0;j<A;j++){
            int b;cin >> b;
            assert(1<=b && b<=N && last<b);
            last=b;
            B[i][b-1]=1;
        }
        cin >> Y[i];
        assert(0<=Y[i] && 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;
        }
        dbg(res);
        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