結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー むらため
提出日時 2019-02-07 12:42:03
言語 Nim
(2.2.0)
結果
WA  
実行時間 -
コード長 3,126 bytes
コンパイル時間 3,014 ms
コンパイル使用メモリ 66,812 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 11:26:29
合計ジャッジ時間 3,895 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 22) Warning: imported and not used: 'strutils' [UnusedImport]

ソースコード

diff # 

import sequtils,math,strutils
# template stopwatch(body) = (let t1 = cpuTime();body;stderr.writeLine "TIME:",(cpuTime() - t1) * 1000,"ms")

# 行列
type Matrix[T] = ref object
  w,h:int
  data: seq[T]
proc `[]`[T](m:Matrix[T],x,y:int):T = m.data[x + y * m.w]
proc `[]`[T](m:var Matrix[T],x,y:int):var T = m.data[x + y * m.w]
proc `[]=`[T](m:var Matrix[T],x,y:int,val:T) = m.data[x + y * m.w] = val
proc newMatrix[T](w,h:int):Matrix[T] =
  new(result)
  result.w = w
  result.h = h
  result.data = newSeq[T](w * h)
proc newMatrix[T](arr:seq[seq[T]]):Matrix[T] =
  new(result)
  result.w = arr[0].len
  result.h = arr.len
  result.data = newSeq[T](result.w * result.h)
  for x in 0..<result.w:
    for y in 0..<result.h:
      result[x,y] = arr[y][x]
proc `$`[T](m:Matrix[T]) : string =
  result = ""
  for y in 0..<m.h:
    result &= "["
    for x in 0..<m.w:
      result &= $m[x,y]
      if x != m.w - 1 : result &= ","
    result &= "]"
    if y != m.h - 1 : result &= "\n"
  result &= "\n"
template mapIt[T](M: Matrix[T],op): untyped =
  type outType = type((var it{.inject.}: T;op))
  var i = 0
  var result = newMatrix[outType](M.w,M.h)
  for y in 0..<M.h:
    for x in 0..<M.w:
      let it {.inject.} = M[x,y]
      result[x,y] = op
  result


proc gaussianElimination(A:Matrix[bool],x:seq[bool]):seq[bool] =
  let n = x.len
  template `^=`(x,y) = x = x xor y
  assert n == A.w and n == A.h
  result = x
  var A = A
  for i in 0..<n:
    if not A[i,i]:
      var ok = false
      for j in (i+1)..<n:
        if not A[i,j] : continue
        for k in i..<n: swap(A[k,i],A[k,j])
        swap(result[i],result[j])
        ok = true
        break
      if not ok :
        if result[i] and toSeq(0..<n).allIt(not A[it,i]) : return @[]
        continue
    for j in (i+1)..<n:
      if not A[i,j]: continue
      for k in i..<n: A[k,j] ^= A[k,i]
      result[j] ^= result[i]
  for i in (n-1).countdown(0):
    if A[i,i]:
      for j in 0..<i:
        if not A[i,j] : continue
        A[i,j] = false
        result[j] ^= result[i]
    else:
      result[i] = false
      for j in 0..<i:
        if not A[i,j] : continue
        A[i,j] = false
  for i in 0..<n:
    if not A[i,i] and result[i]  : return @[]


proc getchar_unlocked():char {. discardable,importc:"getchar_unlocked",header: "<stdio.h>"   .}
proc scan(): int =
  while true:
    let k = getchar_unlocked()
    if k < '0': return
    result = 10 * result + k.ord - '0'.ord

let h = scan()
let w = scan()
proc encode(x,y:int):int = x * h + y
let M = (proc ():Matrix[bool] =
  result = newMatrix[bool](w*h,w*h)
  const dxdy9 :seq[tuple[x,y:int]] = @[(0,1),(1,0),(0,-1),(-1,0),(1,1),(1,-1),(-1,-1),(-1,1),(0,0)]
  for x in 0..<w:
    for y in 0..<h:
      for d in dxdy9:
        let nx = x + d.x
        let ny = y + d.y
        if nx < 0 or ny < 0 or nx >= w or ny >= h : continue
        result[encode(x,y),encode(nx,ny)] = true
)()
var C = newSeq[bool](w*h)
for y in 0..<h:
  for x in 0..<w:
    C[encode(x,y)] = getchar_unlocked() == '1'
    getchar_unlocked()
let A = M.gaussianElimination(C)
if A.len == 0 : echo "Impossible"
else: echo A.mapIt(it.int).sum()
0