Advertisement
Guest User

Untitled

a guest
Jul 20th, 2018
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <unordered_set>
  6. #include <unordered_map>
  7. #include <queue>
  8. #include <deque>
  9. #include <algorithm>
  10. #include <stack>
  11. #include <string>
  12. #include <iomanip>
  13. #include <ctime>
  14. #include <cmath>
  15. #include <sstream>
  16. #include <complex>
  17. #include <fstream>
  18. #include <assert.h>
  19. #include <iomanip>
  20. #include <bitset>
  21.  
  22. #pragma GCC optimize("Ofast")
  23. #pragma GCC optimize("no-stack-protector")
  24. #pragma GCC optimize("unroll-loops")
  25. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  26. #pragma GCC optimize("fast-math")
  27.  
  28. using namespace std;
  29.  
  30. //ifstream in("permutation.in");
  31. //ofstream out("permutation.out");
  32.  
  33. //const long double eps = 1e-7;
  34. const int sz = 305;
  35.  
  36. int n;
  37.  
  38. void gauss(vector<bitset<sz> > &a, bitset<sz> &b) {
  39.     vector<int> must(n);
  40.     vector<int> ind(n, -1);
  41.     vector<int> ans;
  42.     for (int i = 0; i < n; ++i) {
  43.         must[i] = i;
  44.     }
  45.     for (int col = 0, row = 0; col < n && row < n; ++col) {
  46.        // must[row] = row;
  47.         for (int i = row; i < n; ++i) {
  48.             if (a[i][col]) {
  49.                 swap(a[i], a[row]);
  50.                 must[row] = i;
  51.                 must[i] = row;
  52.                 break;
  53.             }
  54.         }
  55.         if (!a[row][col]) {
  56.             continue;
  57.         }
  58.         ind[col] = row;
  59.         for (int i = 0; i < n; ++i) {
  60.             if (i != row && a[i][col]) {
  61.                 a[i] ^= a[row];
  62.             }
  63.         }
  64.         ++row;
  65.     }
  66.     for (int i = 0; i < n; ++i) {
  67.         if (ind[i] == -1) {
  68.             cout << "Multiple solutions";
  69.             return;
  70.         }
  71.     }
  72.     for (int i = 0; i < n; ++i) {
  73.         if (a[i][i]) {
  74.             b ^= a[i];
  75.         }
  76.     }
  77.     if (b != 0) {
  78.         cout << "No solution";
  79.         return;
  80.     }
  81.     for (int i = 0; i < n; ++i) {
  82.         if (a[i][i]) {
  83.             ans.push_back(must[i]);
  84.         }
  85.     }
  86.     sort(ans.begin(), ans.end());
  87.     for (auto now : ans) {
  88.         cout << now << " ";
  89.     }
  90. }
  91.  
  92. int main() {
  93.     ios_base::sync_with_stdio(0);
  94.     cin.tie(0);
  95.     cin >> n;
  96.     vector<bitset<sz> > a(n);
  97.     for (int i = 0; i < n; ++i) {
  98.         for (int j = 0; j < n; ++j) {
  99.             char c;
  100.             cin >> c;
  101.             if (c == '1') {
  102.                 a[j].set(i);
  103.             }
  104.         }
  105.     }
  106.     bitset<sz> b;
  107.     for (int i = 0; i < n; ++i) {
  108.         char c;
  109.         cin >> c;
  110.         if (c == '1') {
  111.             b.set(i);
  112.         }
  113.     }
  114.     gauss(a, b);
  115.     return 0;
  116. }
  117.  
  118. /*2
  119.  2.0 3.0 19.0
  120.  4.0 1.0 23.0*/
  121.  
  122. /*7 9
  123.  1 7
  124.  5 9
  125.  5 7
  126.  5 9
  127.  1 1
  128.  6 8
  129.  3 4*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement