結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
![]() |
提出日時 | 2014-11-24 23:31:54 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 3,102 bytes |
コンパイル時間 | 1,191 ms |
コンパイル使用メモリ | 87,144 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-02 21:17:19 |
合計ジャッジ時間 | 2,051 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <vector>#include <cstdio>#include <sstream>#include <map>#include <string>#include <algorithm>#include <queue>#include <cmath>using namespace std;void print(const vector<vector<int> > &v){int n = v.size();int m = v[0].size();for(int i=0; i<n; i++){for(int j=0; j<m; j++){cerr << v[i][j] << (j==(n-1)? " | " : " ");}cerr << endl ;}cerr << endl;}//A[n*n]*b[n*1] = x[n*1]//A^(-1)[n*n]*x[n*1] = b[n*1]bool gaussian_elimination(vector<vector<int> > &A, vector<vector<int> > &x){bool valid = true;int rank=0;int n = A.size();vector< vector<int> > R = A;for(int i=0; i<n; i++){R[i].insert(R[i].end(), x[i].begin(), x[i].end());}int m = R[0].size();//print(R);//foward//rowfor(int i=0; i<n; i++){//print(R);//pivotint pivot_row = i;int pivot_val = abs(R[i][i]);//choose pivot rowfor(int j=i+1; j<n; j++){if(pivot_val < abs(R[j][i])){pivot_row = j;pivot_val = abs(R[j][i]);}}if(pivot_row != i){swap(R[i], R[pivot_row]);}if(pivot_val == 0){continue;}rank++;{int divisor = 1/R[i][i];//A[i][j] == 0, such that (0 <= j < i)for(int j=i; j<m; j++){R[i][j] *= divisor;R[i][j] += 2;R[i][j] %= 2;}}for(int j=i+1; j<n; j++){int divisor = R[j][i]; // R[j][i]/R[i][i], but R[i][i] is 1.0for(int k=i; k<m; k++){R[j][k] -= R[i][k] * divisor;R[j][k] += 2;R[j][k] %= 2;}}}//print(R);//backward//rowfor(int i=n-1; i>=0; i--){for(int j=i-1; j>=0; j--){int c = R[j][i];for(int k=i; k<m; k++){R[j][k] -= R[i][k] * c;R[j][k] += 2;R[j][k] %= 2;}}}for(int i=0; i<n; i++){if(R[i][n] == 0) continue;bool row_valid = false;for(int j=i; j<m; j++){if(abs(R[i][j]) > 0 && j<n){row_valid = true;break;}}if(row_valid == false && R[i][n] != 0){valid = false;break;}}//print(R);//cerr << "rank is " << rank << endl;//cerr << (valid?"valid":"invalid, no solutions") << endl;return valid;}int main(){int N;cin >> N;vector<int> D(N);for(int i=0; i<N; i++){cin >> D[i];D[i] %= N;}//W[i][0] := i番目のコインをひっくり返さねばならないとき1、それ以外は0vector< vector<int> > W(N, vector<int>(1));for(int i=0; i<N; i++){cin >> W[i][0];//今の状態が表(入力:1)なら裏返す必要はないので0、裏(入力:0)なら裏返す必要があるので1W[i][0] = !W[i][0];}//C[i][j] := j枚目のコインでi番目のコインがひっくり返る場合1、それ以外は0vector< vector<int> > C(N, vector<int>(N, 0));for(int i=0; i<N; i++){C[ (i+D[i])%N ][i] |= 1;C[ (i-D[i]+N)%N ][i] |= 1;}//ガウスの消去法でCx = Wを解いて解が存在するなら"Yes"、そうでなければ"No"cout << (gaussian_elimination(C,W)?"Yes":"No") << endl;return 0;}