Advertisement
Gosunov

Untitled

Sep 23rd, 2022
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(a) (a).begin(), (a).end()
  4. #define double long double
  5.  
  6. int seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  7. mt19937 mt(200);
  8.  
  9. int rnd(int a, int b) {
  10.     return a + mt() % (b - a + 1);
  11. }
  12.  
  13. double prob(double p) {
  14.     return (double)mt() / (double)INT_MAX <= p;
  15. }
  16.  
  17. const int maxn = 205;
  18. int a[maxn][maxn];
  19. int r[maxn];
  20. int c[maxn];
  21. int x[maxn];
  22. int y[maxn];
  23.  
  24. int n, m;
  25.  
  26. void ch_row(int i) {
  27.     x[i] ^= 1;
  28.     r[i] = -r[i];
  29.  
  30.     for (int j = 0; j < m; ++j) {
  31.         c[j] -= a[i][j];
  32.         a[i][j] = -a[i][j];
  33.         c[j] += a[i][j];
  34.     }
  35. }
  36.  
  37. void ch_col(int j) {
  38.     y[j] ^= 1;
  39.     c[j] = -c[j];
  40.  
  41.     for (int i = 0; i < n; ++i) {
  42.         r[i] -= a[i][j];
  43.         a[i][j] = -a[i][j];
  44.         r[i] += a[i][j];
  45.     }
  46. }
  47.  
  48. bool check() {
  49.     for (int i = 0; i < n; ++i) {
  50.         int s = 0;
  51.         for (int j = 0; j < m; ++j)
  52.             s += a[i][j];
  53.         if (s < 0)
  54.             return false;
  55.     }
  56.     for (int j = 0; j < m; ++j) {
  57.         int s = 0;
  58.         for (int i = 0; i < n; ++i)
  59.             s += a[i][j];
  60.         if (s < 0)
  61.             return false;
  62.     }
  63.     return true;
  64. }
  65.  
  66. int f() {
  67.     int ans = 0;
  68.     for (int i = 0; i < n; ++i) {
  69.         ans += r[i] < 0;
  70.     }
  71.     for (int j = 0; j < m; ++j) {
  72.         ans += c[j] < 0;
  73.     }
  74.     return ans;
  75. }
  76.  
  77. void solve() {
  78.     cin >> n >> m;
  79.     for (int i = 0; i < n; ++i) {
  80.         for (int j = 0; j < m; ++j) {
  81.             cin >> a[i][j];
  82.             r[i] += a[i][j];
  83.             c[j] += a[i][j];
  84.         }
  85.     }
  86.    
  87.     double T = 10000;
  88.  
  89.     int fx = f();
  90.     while (fx > 0) {
  91.         T *= 0.99983;
  92.         int tt = mt() & 1;
  93.         int t;
  94.         if (tt) {
  95.             t = rnd(0, n - 1);
  96.             ch_row(t);
  97.         }
  98.         else {
  99.             t = rnd(0, m - 1);
  100.             ch_col(t);
  101.         }
  102.         int fy = f();
  103.         int df = fy - fx;
  104.         if (df < 0) {
  105.             fx = fy;
  106.             continue;
  107.         }
  108.         double p = exp(df / T);
  109.         if (prob(p)) {
  110.             fx = fy;
  111.         } else {
  112.             if (tt)
  113.                 ch_row(t);
  114.             else
  115.                 ch_col(t);
  116.         }
  117.     }
  118.     assert(check());
  119.     vector<int> ans1;
  120.     vector<int> ans2;
  121.     for (int i = 0; i < n; ++i)
  122.         if (x[i]) ans1.push_back(i + 1);
  123.     for (int i = 0; i < m; ++i)
  124.         if (y[i]) ans2.push_back(i + 1);
  125.  
  126.     cout << "Yes\n";
  127.     cout << ans1.size() << '\n';
  128.     for (int i : ans1)
  129.         cout << i << ' ';
  130.     cout << '\n';
  131.  
  132.     cout << ans2.size() << '\n';
  133.     for (int i : ans2)
  134.         cout << i << ' ';
  135.     cout << '\n';
  136. }
  137.  
  138. signed main() {
  139.     ios::sync_with_stdio(0); cin.tie(0);
  140.     int t;
  141.     cin >> t;
  142.     while (t--) {
  143.         solve();
  144.         memset(r, 0, sizeof r);
  145.         memset(c, 0, sizeof c);
  146.         memset(x, 0, sizeof x);
  147.         memset(y, 0, sizeof y);
  148.     }
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement