結果
| 問題 |
No.1566 All Even
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:26:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,742 bytes |
| コンパイル時間 | 769 ms |
| コンパイル使用メモリ | 90,436 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-05-14 13:27:35 |
| 合計ジャッジ時間 | 1,695 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 WA * 10 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <set>
#include <vector>
#include <bitset>
#include <tuple> // Required for std::tuple
// Max variables for Gaussian elimination (k)
// For N=1, k=1. For N=2, k=3. For N=3, k=3.
const int MAX_VARS_GAUSS = 3;
// Solves a system of linear equations over GF(2)
// equations_list is a vector of pairs (mask, value)
// mask indicates which variables are summed (e.g., mask 7 for X0+X1+X2), value is the RHS
// k is the number of variables
long long solve_gf2_system(std::vector<std::pair<int, int>>& equations_list, int k) {
if (k == 0) {
// This case occurs if N>=4 where variables are fixed (all 1s).
// equations_list would check consistency.
// e.g. 0 = 1 means contradiction.
for (const auto& eq : equations_list) {
// For N>=4, all variables are fixed to 1. Any constraint effectively becomes
// a fixed value = z_i. So if this function were called for N>=4, k=0 means no free variables.
// An equation like 0=1 (from 1=0) would mean 0 solutions.
// This part of logic is simplified as N>=4 is handled before calling this.
if (eq.first == 0 && eq.second == 1) return 0;
}
return 1;
}
std::vector<std::bitset<MAX_VARS_GAUSS + 1>> A; // Store augmented matrix
for (const auto& eq_pair : equations_list) {
std::bitset<MAX_VARS_GAUSS + 1> row;
// Fill variable coefficients
for (int i = 0; i < k; ++i) {
if ((eq_pair.first >> i) & 1) {
row[i] = 1;
}
}
// Fill constant term (RHS)
row[k] = eq_pair.second;
A.push_back(row);
}
int num_equations = A.size();
int pivot_row = 0;
// Gaussian elimination
for (int col = 0; col < k && pivot_row < num_equations; ++col) {
int sel_row = pivot_row;
// Find a row with 1 in current column at or below pivot_row
while (sel_row < num_equations && A[sel_row][col] == 0) {
sel_row++;
}
if (sel_row < num_equations) { // If pivot found
std::swap(A[pivot_row], A[sel_row]); // Move pivot row to pivot_row
// Eliminate other 1s in this column by XORing with pivot_row
for (int r = 0; r < num_equations; ++r) {
if (r != pivot_row && A[r][col] == 1) {
A[r] ^= A[pivot_row];
}
}
pivot_row++; // Increment pivot_row counter (this is also current rank)
}
}
int rank = pivot_row; // Rank is the number of pivots found
// Check for inconsistencies (0 = 1) in rows below pivots
for (int i = rank; i < num_equations; ++i) {
// A[i] has all zeros on variable side. If A[i][k] (RHS) is 1, it's 0 = 1.
if (A[i][k] == 1) {
return 0; // Inconsistent system
}
}
// Number of solutions is 2^(number of variables - rank)
return 1LL << (k - rank);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N_in, M_in;
std::cin >> N_in >> M_in;
std::vector<std::tuple<int, int, int>> constraints(M_in);
for (int i = 0; i < M_in; ++i) {
std::cin >> std::get<0>(constraints[i]) >> std::get<1>(constraints[i]) >> std::get<2>(constraints[i]);
}
if (N_in >= 4) {
bool possible = true;
for (int i = 0; i < M_in; ++i) {
// For N>=4, all a_ij must be 1. So z_i must be 1.
if (std::get<2>(constraints[i]) == 0) {
possible = false;
break;
}
}
if (possible) {
std::cout << 1 << std::endl;
} else {
std::cout << 0 << std::endl;
}
return 0;
}
std::vector<std::pair<int, int>> equations_list;
int k_vars = 0;
if (N_in == 1) {
k_vars = 1; // Variable X_0 = a_1,1
for (int i = 0; i < M_in; ++i) {
// Constraint a_x,y = z becomes a_1,1 = z (since x=1,y=1 for N=1)
// Equation: X_0 = z. Mask for X_0 is (1 << 0) = 1.
equations_list.push_back({(1 << 0), std::get<2>(constraints[i])});
}
} else if (N_in == 2) {
k_vars = 3; // Variables: X_0=a_1,1, X_1=a_1,2, X_2=a_2,1
for (int i = 0; i < M_in; ++i) {
int r = std::get<0>(constraints[i]);
int c = std::get<1>(constraints[i]);
int val = std::get<2>(constraints[i]);
if (r == 1 && c == 1) { // a_1,1 = val => X_0 = val
equations_list.push_back({(1 << 0), val});
} else if (r == 1 && c == 2) { // a_1,2 = val => X_1 = val
equations_list.push_back({(1 << 1), val});
} else if (r == 2 && c == 1) { // a_2,1 = val => X_2 = val
equations_list.push_back({(1 << 2), val});
} else if (r == 2 && c == 2) { // a_2,2 = val. And a_2,2 = X_0+X_1+X_2. So X_0+X_1+X_2 = val
equations_list.push_back({(1 << 0) | (1 << 1) | (1 << 2), val});
}
}
} else if (N_in == 3) {
k_vars = 3; // Variables: X_0=a_1,1, X_1=a_2,1, X_2=a_1,2
// Intrinsic equation from structure of N=3 matrices: X_0 + X_1 + X_2 = 1
equations_list.push_back({(1 << 0) | (1 << 1) | (1 << 2), 1});
for (int i = 0; i < M_in; ++i) {
int r = std::get<0>(constraints[i]);
int c = std::get<1>(constraints[i]);
int val = std::get<2>(constraints[i]);
// Mapping (r,c) to expressions in X_0, X_1, X_2 for N=3 case:
// a_1,1=X_0, a_1,2=X_2, a_1,3=X_0
// a_2,1=X_1, a_2,2=1, a_2,3=X_1
// a_3,1=X_0, a_3,2=X_2, a_3,3=X_0
if ((r == 1 && c == 1) || (r == 1 && c == 3) || (r == 3 && c == 1) || (r == 3 && c == 3)) {
// This cell value is X_0. So X_0 = val.
equations_list.push_back({(1 << 0), val});
} else if ((r == 2 && c == 1) || (r == 2 && c == 3)) {
// This cell value is X_1. So X_1 = val.
equations_list.push_back({(1 << 1), val});
} else if ((r == 1 && c == 2) || (r == 3 && c == 2)) {
// This cell value is X_2. So X_2 = val.
equations_list.push_back({(1 << 2), val});
} else if (r == 2 && c == 2) {
// This cell value is 1 (from template). So 1 = val.
// This is equivalent to 0 = val XOR 1.
equations_list.push_back({0, (val ^ 1)});
}
}
}
std::cout << solve_gf2_system(equations_list, k_vars) << std::endl;
return 0;
}