Advertisement
supremeXD

Untitled

Oct 15th, 2021
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <bitset>
  5. using namespace std;
  6.  
  7. #define all(v) v.begin(), v.end()
  8.  
  9. int main() {
  10. int n, k; cin >> n >> k; // количество переменных в скобках, количество скобок
  11. vector<vector<int>>f(k, vector<int>(n));
  12. for (int i = 0; i < k; i++) {
  13. for (int j = 0; j < n; j++) {
  14. cin >> f[i][j]; // 0 - отрицание переменной, 1 - переменная, -1 - отсутствие переменной
  15. }
  16. }
  17. vector<vector<int>>given = f;
  18. int cnt = 0;
  19. vector<int>x(n, -1);
  20. while (cnt < 10000000) {
  21. bool saw_only_one = false;
  22. for (int i = 0; i < k; i++) {
  23. int only_one = 0; // 0 - not_see, 1 - only_one, 2+ - more than one
  24. for (int j = 0; j < n; j++) {
  25. if (f[i][j] != -1) {
  26. only_one++;
  27. }
  28. }
  29. if (only_one == 1) {
  30. saw_only_one = true;
  31. for (int j = 0; j < n; j++) {
  32. if (f[i][j] == 0) {
  33. f[i][j] = -1;
  34. x[j] = 0;
  35. break;
  36. } else if (f[i][j] == 1) {
  37. f[i][j] = -1;
  38. x[j] = 1;
  39. break;
  40. }
  41. }
  42. }
  43. }
  44. if (saw_only_one == false) {
  45. for (int i = 0; i < n; i++) {
  46. x[i] = 0;
  47. }
  48. break;
  49. }
  50. cnt++;
  51. }
  52.  
  53. for (int i = 0; i < x.size(); i++) {
  54. if(x[i] == -1) {
  55. cout << "YES\n";
  56. return 0;
  57. }
  58. }
  59.  
  60. for (int i = 0; i < f.size(); i++) {
  61. bool all_minus_one = true;
  62. for (int j = 0; j < f[i].size(); j++) {
  63. if (f[i][j] != -1) {
  64. all_minus_one = false;
  65. }
  66. }
  67. if (all_minus_one == true) {
  68. cout << "YES\n";
  69. return 0;
  70. }
  71. }
  72.  
  73. for (int i = 0; i < k; i++) {
  74. int result = 0;
  75. for (int j = 0; j < n; j++) {
  76. if (given[i][j] == -1) {
  77. continue;
  78. } else if (given[i][j] == 0) {
  79. result = result | !x[j];
  80. } else if (given[i][j] == 1) {
  81. result = result | x[j];
  82. }
  83. }
  84. if (result == 0) {
  85. cout << "YES\n";
  86. return 0;
  87. }
  88. }
  89.  
  90. cout << "NO\n";
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement