Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define all(a) (a).begin(), (a).end()
- #define double long double
- int seed = chrono::high_resolution_clock::now().time_since_epoch().count();
- mt19937 mt(200);
- int rnd(int a, int b) {
- return a + mt() % (b - a + 1);
- }
- double prob(double p) {
- return (double)mt() / (double)INT_MAX <= p;
- }
- const int maxn = 205;
- int a[maxn][maxn];
- int r[maxn];
- int c[maxn];
- int x[maxn];
- int y[maxn];
- int n, m;
- void ch_row(int i) {
- x[i] ^= 1;
- r[i] = -r[i];
- for (int j = 0; j < m; ++j) {
- c[j] -= a[i][j];
- a[i][j] = -a[i][j];
- c[j] += a[i][j];
- }
- }
- void ch_col(int j) {
- y[j] ^= 1;
- c[j] = -c[j];
- for (int i = 0; i < n; ++i) {
- r[i] -= a[i][j];
- a[i][j] = -a[i][j];
- r[i] += a[i][j];
- }
- }
- bool check() {
- for (int i = 0; i < n; ++i) {
- int s = 0;
- for (int j = 0; j < m; ++j)
- s += a[i][j];
- if (s < 0)
- return false;
- }
- for (int j = 0; j < m; ++j) {
- int s = 0;
- for (int i = 0; i < n; ++i)
- s += a[i][j];
- if (s < 0)
- return false;
- }
- return true;
- }
- int f() {
- int ans = 0;
- for (int i = 0; i < n; ++i) {
- ans += r[i] < 0;
- }
- for (int j = 0; j < m; ++j) {
- ans += c[j] < 0;
- }
- return ans;
- }
- void solve() {
- cin >> n >> m;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- cin >> a[i][j];
- r[i] += a[i][j];
- c[j] += a[i][j];
- }
- }
- double T = 10000;
- int fx = f();
- while (fx > 0) {
- T *= 0.99983;
- int tt = mt() & 1;
- int t;
- if (tt) {
- t = rnd(0, n - 1);
- ch_row(t);
- }
- else {
- t = rnd(0, m - 1);
- ch_col(t);
- }
- int fy = f();
- int df = fy - fx;
- if (df < 0) {
- fx = fy;
- continue;
- }
- double p = exp(df / T);
- if (prob(p)) {
- fx = fy;
- } else {
- if (tt)
- ch_row(t);
- else
- ch_col(t);
- }
- }
- assert(check());
- vector<int> ans1;
- vector<int> ans2;
- for (int i = 0; i < n; ++i)
- if (x[i]) ans1.push_back(i + 1);
- for (int i = 0; i < m; ++i)
- if (y[i]) ans2.push_back(i + 1);
- cout << "Yes\n";
- cout << ans1.size() << '\n';
- for (int i : ans1)
- cout << i << ' ';
- cout << '\n';
- cout << ans2.size() << '\n';
- for (int i : ans2)
- cout << i << ' ';
- cout << '\n';
- }
- signed main() {
- ios::sync_with_stdio(0); cin.tie(0);
- int t;
- cin >> t;
- while (t--) {
- solve();
- memset(r, 0, sizeof r);
- memset(c, 0, sizeof c);
- memset(x, 0, sizeof x);
- memset(y, 0, sizeof y);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement