結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー te-sh
提出日時 2017-12-07 12:30:05
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 2,044 bytes
コンパイル時間 727 ms
コンパイル使用メモリ 105,668 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-12 22:51:45
合計ジャッジ時間 1,580 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.math;      // math functions

void main()
{
  auto rd = readln.split.to!(int[]), m = rd[0], n = rd[1], mn = m*n;

  auto a = new bool[](mn);
  foreach (i; 0..m) {
    auto ai = readln.split;
    foreach (j; 0..n)
      a[i*n+j] = ai[j] == "1";
  }

  auto b = new ulong[](mn);
  foreach (i; 0..mn)
    foreach (j; 0..mn) {
      auto r1 = i/n, c1 = i%n, r2 = j/n, c2 = j%n;
      if ((r1-r2).abs <= 1 && (c1-c2).abs <= 1)
        b[i] = b[i].bitSet(j);
    }

  auto k = 0;
  foreach (i; 0..mn) {
    while (k < mn && !b[i].bitTest(k)) {
      auto j = b[i+1..$].countUntil!(bj => bj.bitTest(k));
      if (j >= 0) {
        swap(b[i], b[i+j+1]);
        swap(a[i], a[i+j+1]);
        break;
      }
      ++k;
    }
    if (k == mn) break;
    foreach (j; i+1..mn)
      if (b[j].bitTest(k)) {
        b[j] ^= b[i];
        a[j] ^= a[i];
      }
    ++k;
  }

  auto x = new bool[](mn);
  foreach_reverse (i; 0..mn) {
    if (b[i] == 0) {
      if (a[i]) {
        writeln("Impossible");
        return;
      }
    } else {
      k = b[i].bsf;
      x[k] = a[i];
      foreach (j; k+1..mn)
        x[k] ^= (x[j] & b[i].bitTest(j));
    }
  }

  writeln(x.count(true));
}

pragma(inline) {
  pure bool bitTest(T)(T n, size_t i) { return (n & (T(1) << i)) != 0; }
  pure T bitSet(T)(T n, size_t i) { return n | (T(1) << i); }
  pure T bitReset(T)(T n, size_t i) { return n & ~(T(1) << i); }
  pure T bitComp(T)(T n, size_t i) { return n ^ (T(1) << i); }

  pure T bitSet(T)(T n, size_t s, size_t e) { return n | ((T(1) << e) - 1) & ~((T(1) << s) - 1); }
  pure T bitReset(T)(T n, size_t s, size_t e) { return n & (~((T(1) << e) - 1) | ((T(1) << s) - 1)); }
  pure T bitComp(T)(T n, size_t s, size_t e) { return n ^ ((T(1) << e) - 1) & ~((T(1) << s) - 1); }

  import core.bitop;
  pure int bsf(T)(T n) { return core.bitop.bsf(ulong(n)); }
  pure int bsr(T)(T n) { return core.bitop.bsr(ulong(n)); }
  pure int popcnt(T)(T n) { return core.bitop.popcnt(ulong(n)); }
}
0