fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define f first
  6. #define s second
  7. #define pb push_back
  8. #define endl '\n'
  9. #define sz(x) (int)x.size()
  10. //#define all(x) x.begin(), x.end()
  11. typedef long long ll;
  12. typedef pair<int, int> pii;
  13. typedef pair<pii, int> pip;
  14. typedef unsigned long long ull;
  15. const int mxn = 5e3+5;
  16. const int mxm = 1e5+5;
  17. const int MOD = 1e9+7;
  18. const int INF = 0x3f3f3f3f;
  19. const ll INFL = 0x3f3f3f3f3f3f3f3f;
  20.  
  21. // Returns -1 if a < b, 0 if a = b and 1 if a > b.
  22. int cmp_double(double a, double b = 0, double eps = 1e-9) {
  23.     return a + eps > b ? b + eps > a ? 0 : 1 : -1;
  24. }
  25.  
  26. typedef bitset<1502> bs;
  27. bool gauss(vector<bs> &a, bs& ans, int n) {
  28. 	int m = int(a.size()), c = 0;
  29. 	bs pos; pos.set();
  30. 	for (int j = n-1, i; j >= 0; --j) {
  31. 		for (i = c; i < m; ++i)
  32. 			if (a[i][j]) break;
  33. 		if (i == m) continue;
  34. 		swap(a[c], a[i]);
  35. 		i = c++; pos[j] = 0;
  36. 		for (int k = 0; k < m; ++k)
  37. 			if (a[k][j] && k != i) a[k] ^= a[i];
  38. 	} ans = pos;
  39. 	for(int i = 0; i < m; ++i) {
  40. 		int ac = 0;
  41. 		for (int j = 0; j < n ; ++j) {
  42. 			if (!a[i][j]) continue;
  43. 			if (!pos[j]) pos[j] = 1, ans[j] = ac^a[i][n];
  44. 			ac ^= ans[j];
  45. 		}
  46. 		if (ac != a[i][n]) return false;
  47. 	}
  48. 	return true;
  49. }
  50.  
  51. signed cases(){
  52.     int n, k;
  53.     cin >> n >> k;
  54.     vector<bs> ab(k+1), tmp(n);
  55.     for(int i=0; i<n; i++){
  56.         string a;
  57.         cin >> a;
  58.         bs mask;
  59.         mask[k] = 1;
  60.         for(int j = k-1; j>=0; j--){
  61.             mask[j] = a[k - j - 1] - '0';
  62.         }
  63.         tmp[i] = mask;
  64.     }
  65.     for(int i=0; i<n; i++){
  66.         for(int j=0; j<=k; j++){
  67.             ab[j][i] = tmp[i][j];
  68.         }
  69.     }
  70.     bs ans;
  71.     if(gauss(ab, ans, k+1)){
  72.         vector<int> resp(n);
  73.         int cont = 0;
  74.         for(int i=0; i<n; i++){
  75.             if(ans[i]) {resp[i] = cont%2 + 1; cont++;} 
  76.         }
  77.         if(!cont || cont&1){
  78.             cout << '*' << endl;
  79.         }else{
  80.             for(int i:resp) cout << i;
  81.             cout << endl;
  82.         }
  83.     }else{
  84.         cout << '*' << endl;
  85.     }
  86.     return 0;
  87. }
  88.  
  89. signed main(){
  90.     ios_base::sync_with_stdio(false), cin.tie(nullptr);
  91.     int t=1;
  92.  
  93.     //cin >> t;
  94.  
  95.     for(int i=1; i<=t; i++){
  96.         //cout << "Case #" << i << ": ";
  97.         cases();
  98.     }
  99.     return 0;
  100. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
*
https://ideone.com/M9DSjX
language:
C++14 (gcc 8.3)
created:
280 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!