結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー yuppe19 😺
提出日時 2016-12-26 00:02:10
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,138 bytes
コンパイル時間 433 ms
コンパイル使用メモリ 53,664 KB
最終ジャッジ日時 2024-11-14 19:55:18
合計ジャッジ時間 982 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:12:17: error: ‘vector’ was not declared in this scope
   12 | tuple<int, int, vector<int>> mod2_gauss_elimination(const vector<vector<int>> &A, const vector<int> &b) {
      |                 ^~~~~~
main.cpp:4:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    3 | #include <tuple>
  +++ |+#include <vector>
    4 | using namespace std;
main.cpp:12:27: error: template argument 3 is invalid
   12 | tuple<int, int, vector<int>> mod2_gauss_elimination(const vector<vector<int>> &A, const vector<int> &b) {
      |                           ^~
main.cpp:12:59: error: ‘vector’ does not name a type
   12 | tuple<int, int, vector<int>> mod2_gauss_elimination(const vector<vector<int>> &A, const vector<int> &b) {
      |                                                           ^~~~~~
main.cpp:12:65: error: expected ‘,’ or ‘...’ before ‘<’ token
   12 | tuple<int, int, vector<int>> mod2_gauss_elimination(const vector<vector<int>> &A, const vector<int> &b) {
      |                                                                 ^
main.cpp: In function ‘int mod2_gauss_elimination(int)’:
main.cpp:13:17: error: ‘A’ was not declared in this scope
   13 |   const int n = A.size();
      |                 ^
main.cpp:14:3: error: ‘vector’ was not declared in this scope
   14 |   vector<vector<int>> B(n, vector<int>(n+1));
      |   ^~~~~~
main.cpp:14:3: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
main.cpp:14:17: error: expected primary-expression before ‘int’
   14 |   vector<vector<int>> B(n, vector<int>(n+1));
      |                 ^~~
main.cpp:16:30: error: ‘B’ was not declared in this scope
   16 |     for(int j=0; j<n; ++j) { B[i][j] = A[i][j]; }
      |                              ^
main.cpp:17:5: error: ‘B’ was not declared in this scope
   17 |     B[i][n] = b[i];
      |     ^
main.cpp:17:15: error: ‘b�

ソースコード

diff # 

#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;
}
0