#141429 (C++11(old_compat)) No.460 裏表ちわーわ

• 問題: No.460 裏表ちわーわ
• ユーザー: yuppe19 😺
• 提出日時: 2016-12-26 00:02:10
• 言語: C++11(old_compat) (gcc 12.4.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 50 ms / 2,000 ms
• コード長: 3,138 bytes
• コンパイル時間: 1,455 ms
• コンパイル使用メモリ: 180,256 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2026-03-08 16:08:10
• 合計ジャッジ時間: 2,260 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 28

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:90:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   90 |   int R, C; scanf("%d%d", &R, &C);
      |             ~~~~~^~~~~~~~~~~~~~~~
main.cpp:95:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   95 |       scanf("%d", &b[r*C+c]);
      |       ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;

constexpr int INF = 987654321;

// 戻り値
// ひとつめ: status(int) 0: 解なし, 1: 解が一意に決まった, 2: 解が複数あって一意に決まらない
// ふたつめ: cnt(int): 手数。解が複数あるときは最小手数。
// みっつめ: arr(vector<int>): 解。複数あるときはそのうちのどれかひとつ
tuple<int, int, vector<int>> mod2_gauss_elimination(const vector<vector<int>> &A, const vector<int> &b) {
  const int n = A.size();
  vector<vector<int>> B(n, vector<int>(n+1));
  for(int i=0; i<n; ++i) {
    for(int j=0; j<n; ++j) { B[i][j] = A[i][j]; }
    B[i][n] = b[i];
  }
  int curr = 0;
  for(int c=0; c<n; ++c) {
    int pivot = -1;
    for(int r=curr; r<n; ++r) {
      if(B[r][c]) {
        pivot = r;
        break;
      }
    }
    if(pivot == -1) { continue; }
    swap(B[curr], B[pivot]);
    for(int r=curr+1; r<n; ++r) {
      if(B[r][c]) {
        for(int nc=c; nc<=n; ++nc) {
          B[r][nc] ^= B[curr][nc];
        }
      }
    }
    ++curr;
  }

  vector<int> v;
  for(int r=curr; r<n; ++r) {
    if(B[r][n]) { // rank(A) != rank(A|b)
      return make_tuple(0, -1, v);
    }
  }
  if(curr < n) { // rank(A) == rank(A|b) != n
    // 解が一意でない。ひとつ求める
    int mini = INF;
    vector<int> arr;
    for(int mask=0; mask<1<<(n-curr); ++mask) {
      v.assign(n, -1); // -1 は任意を表す
      int cnt = __builtin_popcount(mask);
      for(int r=curr, k=0; r>=0 && cnt<mini; --r) {
        int i;
        for(i=r; i<n; ++i) {
          if(B[r][i]) { break; }
        }
        if(i == n) { continue; }
        v[i] = B[r][n];
        for(int c=i+1; c<n; ++c) {
          // この時点で v[c] が決まってなかったらこれは任意だということなので、勝手に決める
          if(v[c] == -1) { v[c] = mask >> k++ & 1; }
          v[i] ^= v[c] & B[r][c];
        }
        if(v[i]) { ++cnt; }
      }
      if(mini > cnt) {
        mini = cnt;
//        arr = v;
      }
    }
    return make_tuple(2, mini, arr);
  }
  // 解が一意に決まる。普通に後退代入
  v.assign(n, 0);
  for(int r=n-1; r>=0; --r) {
    v[r] = B[r][n];
    for(int c=n-1; c>r; --c) {
      v[r] ^= v[c] & B[r][c];
    }
  }
  int cnt = 0;
  for(int i=0; i<n; ++i) {
    if(v[i]) { ++cnt; }
  }
  return make_tuple(1, cnt, v);
}

int main(void) {
  int R, C; scanf("%d%d", &R, &C);
  int n = R * C;
  vector<int> b(n);
  for(int r=0; r<R; ++r) {
    for(int c=0; c<C; ++c) {
      scanf("%d", &b[r*C+c]);
    }
  }
  vector<vector<int>> A(n, vector<int>(n));
  for(int r=0; r<R; ++r) {
    for(int c=0; c<C; ++c) {
      for(int dr=-1; dr<=1; ++dr) {
        for(int dc=-1; dc<=1; ++dc) {
          int nr = r + dr,
              nc = c + dc;
          if(!(0 <= nr && nr < R && 0 <= nc && nc < C)) { continue; }
          A[r*C+c][nr*C+nc] = 1;
        }
      }
    }
  }
  int status, cnt; vector<int> _;
  tie(status, cnt, _) = mod2_gauss_elimination(A, b);
  if(!status) {
    puts("Impossible");
  } else {
    printf("%d\n", cnt);
  }
  return 0;
}