結果

問題 No.74 貯金箱の退屈
コンテスト
ユーザー koba-e964
提出日時 2015-06-08 18:28:07
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,439 bytes
コンパイル時間 524 ms
コンパイル使用メモリ 66,500 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 14:48:47
合計ジャッジ時間 1,430 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <vector>


class GF2Matrix {
private:
  std::vector<std::vector<bool> > mat;
  int n, m;
public:
  GF2Matrix(int n, int m) : n(n), m(m), mat(n) {
    for (int i = 0; i < n; ++i) {
      mat[i] = std::vector<bool>(m);
    }
  }
  std::vector<bool> &operator[](int i) {
    return mat[i];
  }
  const std::vector<bool> &operator[](int i) const {
    return mat[i];
  }
  /* Returns the rank of this matrix. */
  int eliminate(void) {
    int r = 0;
    for (int c = 0; c < m; ++c) {
      int r1 = -1;
      for (int i = r; i < n; ++i) {
	if (mat[i][c]) {
	  r1 = i;
	  break;
	}
      }
      if (r1 == -1) {
	continue;
      }
      std::swap(mat[r], mat[r1]);
      for (int i = 0; i < n; ++i) {
	if (i != r && mat[i][c]) {
	  for (int j = c; j < m; ++j) {
	    mat[i][j] = mat[i][j] ^ mat[r][j];
	  }
	}
      }
      ++r;
    }
    return r;
  }
};
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#include <iostream>

using namespace std;

int main(void){
  int n;
  cin >> n;
  GF2Matrix mat(n, n + 1);
  REP(i, 0, n) {
    int d;
    cin >> d;
    int r1 = (i + d) % n;
    int r2 = (i - d % n + n) % n;
    mat[r1][i] = 1;
    mat[r2][i] = 1;
  }
  REP(i, 0, n) {
    int w;
    cin >> w;
    mat[i][n] = 1 - w;
  }
  int r = mat.eliminate();
  bool ok = 0;
  if (r >= 1) {
    REP(i, 0, n) {
      ok |= mat[r - 1][i];
    }
    ok |= !mat[r - 1][n];
  }
  cout << (ok ? "Yes" : "No") << endl;
}
0