#3580 (C++11) No.74 貯金箱の退屈

• 問題: No.74 貯金箱の退屈
• ユーザー: koyumeishi
• 提出日時: 2014-11-24 23:28:09
• 言語: C++11 (gcc 11.4.0)
• 結果: RE
• 実行時間: -
• コード長: 3,018 bytes
• コンパイル時間: 922 ms
• コンパイル使用メモリ: 83,224 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-06-10 22:06:08
• 合計ジャッジ時間: 5,769 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	1 ms; 6,812 KB
testcase_02	AC	1 ms; 6,944 KB
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-

ソースコード

#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
	//row
	for(int i=0; i<n; i++){

		//print(R);
		
		//pivot
		int pivot_row = i;
		int pivot_val = abs(R[i][i]);
		//choose pivot row
		for(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;
			}
		}
		
		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.0
			for(int k=i; k<m; k++){
				R[j][k] -= R[i][k] * divisor;
				R[j][k] %= 2;
			}
		}
	}

	//print(R);

	//backward
	//row
	for(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;
			}
		}
	}

	for(int i=0; i<n; i++){
		bool row_valid = false;
		for(int j=i; j<m; j++){
			if(abs(R[i][j]) <= 1e-9){
				R[i][j] = 0.0;
			}else if(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];
	}

	//W[i][0] := i番目のコインをひっくり返さねばならないとき1、それ以外は0
	vector< vector<int> > W(N, vector<int>(1));
	for(int i=0; i<N; i++){
		cin >> W[i][0];
		//今の状態が表(入力:1)なら裏返す必要はないので0、裏(入力:0)なら裏返す必要があるので1
		W[i][0] = !W[i][0];
	}

	//C[i][j] := j枚目のコインでi番目のコインがひっくり返る場合1、それ以外は0
	vector< 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;
}