Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- #include <queue>
- #include <deque>
- #include <algorithm>
- #include <stack>
- #include <string>
- #include <iomanip>
- #include <ctime>
- #include <cmath>
- #include <sstream>
- #include <complex>
- #include <fstream>
- #include <assert.h>
- #include <iomanip>
- #include <bitset>
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #pragma GCC optimize("fast-math")
- using namespace std;
- //ifstream in("permutation.in");
- //ofstream out("permutation.out");
- //const long double eps = 1e-7;
- const int sz = 305;
- int n;
- void gauss(vector<bitset<sz> > &a, bitset<sz> &b) {
- vector<int> must(n);
- vector<int> ind(n, -1);
- vector<int> ans;
- for (int i = 0; i < n; ++i) {
- must[i] = i;
- }
- for (int col = 0, row = 0; col < n && row < n; ++col) {
- // must[row] = row;
- for (int i = row; i < n; ++i) {
- if (a[i][col]) {
- swap(a[i], a[row]);
- must[row] = i;
- must[i] = row;
- break;
- }
- }
- if (!a[row][col]) {
- continue;
- }
- ind[col] = row;
- for (int i = 0; i < n; ++i) {
- if (i != row && a[i][col]) {
- a[i] ^= a[row];
- }
- }
- ++row;
- }
- for (int i = 0; i < n; ++i) {
- if (ind[i] == -1) {
- cout << "Multiple solutions";
- return;
- }
- }
- for (int i = 0; i < n; ++i) {
- if (a[i][i]) {
- b ^= a[i];
- }
- }
- if (b != 0) {
- cout << "No solution";
- return;
- }
- for (int i = 0; i < n; ++i) {
- if (a[i][i]) {
- ans.push_back(must[i]);
- }
- }
- sort(ans.begin(), ans.end());
- for (auto now : ans) {
- cout << now << " ";
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- vector<bitset<sz> > a(n);
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- char c;
- cin >> c;
- if (c == '1') {
- a[j].set(i);
- }
- }
- }
- bitset<sz> b;
- for (int i = 0; i < n; ++i) {
- char c;
- cin >> c;
- if (c == '1') {
- b.set(i);
- }
- }
- gauss(a, b);
- return 0;
- }
- /*2
- 2.0 3.0 19.0
- 4.0 1.0 23.0*/
- /*7 9
- 1 7
- 5 9
- 5 7
- 5 9
- 1 1
- 6 8
- 3 4*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement