結果
問題 | No.1421 国勢調査 (Hard) |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-20 13:56:53 |
言語 | Go (1.22.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,752 bytes |
コンパイル時間 | 12,833 ms |
コンパイル使用メモリ | 236,484 KB |
実行使用メモリ | 9,948 KB |
最終ジャッジ日時 | 2024-09-18 14:03:44 |
合計ジャッジ時間 | 18,015 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 103 ms
8,832 KB |
testcase_28 | AC | 105 ms
8,832 KB |
testcase_29 | AC | 100 ms
8,832 KB |
testcase_30 | AC | 100 ms
8,832 KB |
testcase_31 | AC | 103 ms
8,832 KB |
ソースコード
package main import ( "bufio" "fmt" "os" ) func main() { // https://yukicoder.me/problems/no/1421 in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, m int fmt.Fscan(in, &n, &m) A := make([]*BS, m) for i := range A { A[i] = NewBS(50) } rhs := make([][]int, 30) for i := range rhs { rhs[i] = make([]int, m) } for i := 0; i < m; i++ { var r int fmt.Fscan(in, &r) for j := 0; j < r; j++ { var c int fmt.Fscan(in, &c) A[i].Set(c - 1) } var y int fmt.Fscan(in, &y) for k := 0; k < 30; k++ { rhs[k][i] = y >> k & 1 } } res := make([]int, n) for k := 0; k < 30; k++ { b := rhs[k] x := SolveLinear(m, n, A, b) if x == nil { fmt.Fprintln(out, -1) return } for i := 0; i < n; i++ { if x[0].Get(i) == 1 { res[i] |= 1 << k } } } for _, x := range res { fmt.Fprintln(out, x) } } // 求解线性方程组 Ax = b // 其中行向量用bitset表示 // A: 行向量组成的数组 // b: 0/1组成的数组 // 如果不存在解,返回nil func SolveLinear(n, m int, A []*BS, b []int) []*BS { if len(b) != n { panic("len(b) != n") } if len(A) == 0 { return nil } rk := 0 for j := 0; j < m; j++ { if rk == n { break } for i := rk; i < n; i++ { if A[i].Get(j) == 1 { if i != rk { A[rk], A[i] = A[i], A[rk] if b[rk] != b[i] { b[rk] ^= 1 b[i] ^= 1 } } break } } if A[rk].Get(j) == 0 { continue } for i := 0; i < n; i++ { if i != rk && A[i].Get(j) == 1 { b[i] ^= b[rk] A[i].Xor(A[rk]) } } rk++ } for i := rk; i < n; i++ { if b[i] != 0 { return nil } } size := A[0].n res := make([]*BS, 1) res[0] = NewBS(size) pivot := make([]int, m) for i := range pivot { pivot[i] = -1 } p := 0 for i := 0; i < rk; i++ { for A[i].Get(p) == 0 { p++ } if b[i] == 1 { res[0].Set(p) } else { res[0].Reset(p) } pivot[p] = i } for j := 0; j < m; j++ { if pivot[j] == -1 { x := NewBS(size) x.Set(j) for k := 0; k < j; k++ { if pivot[k] != -1 { num := A[pivot[k]].Get(j) if num == 1 { x.Set(k) } else { x.Reset(k) } } } res = append(res, x) } } return res } type BS struct { n int block []int sum []int } func NewBS(n int) *BS { blockCount := (n + 63) >> 6 return &BS{ n: n, block: make([]int, blockCount), sum: make([]int, blockCount), } } func (f *BS) Set(i int) { f.block[i>>6] |= 1 << uint(i&63) } func (f *BS) Reset(i int) { f.block[i>>6] &^= 1 << uint(i&63) } func (f *BS) Get(i int) int { return (f.block[i>>6] >> uint(i&63)) & 1 } func (f *BS) Xor(g *BS) { for i := range f.block { f.block[i] ^= g.block[i] } }