oj.uz

Submission #899089

# Submission time Handle Problem Language Result Execution time Memory
899089 2024-01-05T13:13:49 Z d4xn Red-blue table (IZhO19_stones) C++17
100 / 100
 1655 ms 3664 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
 
const int N = 1e3;
 
int t, n, m, x, ans, r[N], c[N];
char a[2][N][N];
string b[3];
 
int f() {
  for (int i = 0; i < n; i++) {
    r[i] = 0;
  }
  for (int i = 0; i < m; i++) {
    c[i] = 0;
  }
 
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[1][i][j] == '+') r[i]++;
      else c[j]++;
    }
  }
 
  int y = 0;
  for (int i = 0; i < n; i++) {
    y += (r[i] > m/2);
  }
  for (int i = 0; i < m; i++) {
    y += (c[i] > n/2);
  }
  return y;
}
 
signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> t;
  while (t--) {
    cin >> n >> m;
    ans = 0;
 
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          a[1][i][j] = '+';
        }
      }
 
      vector<int> cnt(n, m);
      for (int j = 0; j < m; j++) {
        vector<pair<int, int>> pos;
        for (int i = 0; i < n; i++) {
          pos.push_back(make_pair(-cnt[i], i));
        }
        sort(all(pos));
 
        for (int i = 0; i <= n/2; i++) {
          int y = -pos[i].first;
          if (y-1 <= m/2) continue;
          cnt[pos[i].second]--;
          a[1][pos[i].second][j] = '-';
        }
      }
 
      x = f();
      if (x > ans) {
        ans = x;
        swap(a[0], a[1]);
      }
 
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          a[1][i][j] = '-';
        }
      }
      
      //vector<int> cnt;
      cnt.clear();
      cnt.resize(m, n);
      for (int i = 0; i < n; i++) {
        vector<pair<int, int>> pos;
        for (int j = 0; j < m; j++) {
          pos.push_back(make_pair(-cnt[j], j));
        }
        sort(all(pos));
 
        for (int j = 0; j <= m/2; j++) {
          int y = -pos[j].first;
          if (y-1 <= n/2) continue;
          cnt[pos[j].second]--;
          a[1][i][pos[j].second] = '+';
        }
      }
 
      x = f();
      if (x > ans) {
        ans = x;
        swap(a[0], a[1]);
      }
 
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        a[1][i][j] = '+';
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if ((i <= n/2 && j < m/2) || (i >= n/2 && j > m/2)) a[1][i][j] = '-';
      }
    }
    x = f();
    if (x > ans) {
      ans = x;
      swap(a[0], a[1]);
    }
 
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        a[1][i][j] = '+';
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if ((i < n/2 && j <= m/2) || (i > n/2 && j >= m/2)) a[1][i][j] = '+';
      }
    }
    x = f();
    if (x > ans) {
      ans = x;
      swap(a[0], a[1]);
    }
 
    cout << ans << "\n";
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << a[0][i][j];
      }
      cout << "\n";
    }
 
    if (n%2 == 1 && m%2 == 1) {
      
    }
    else if (n == m) {
 
    }
    else if (n%2 == 0 && m%2 == 1) {
 
    }
    else if (n%2 == 1 && m%2 == 0) {
 
    }
    else if (n%2 == 1 && m%2 == 1) {
 
    }
  }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2392 KB Output is correct
2 Correct 29 ms 2648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 2644 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2392 KB Output is correct
2 Correct 29 ms 2648 KB Output is correct
3 Correct 585 ms 2644 KB Output is correct
4 Correct 965 ms 2668 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 3408 KB Output is correct
2 Correct 81 ms 3156 KB Output is correct
3 Correct 79 ms 3152 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 3664 KB Output is correct
2 Correct 75 ms 3032 KB Output is correct
3 Correct 66 ms 3156 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2392 KB Output is correct
2 Correct 29 ms 2648 KB Output is correct
3 Correct 585 ms 2644 KB Output is correct
4 Correct 965 ms 2668 KB Output is correct
5 Correct 847 ms 3408 KB Output is correct
6 Correct 81 ms 3156 KB Output is correct
7 Correct 79 ms 3152 KB Output is correct
8 Correct 257 ms 3664 KB Output is correct
9 Correct 75 ms 3032 KB Output is correct
10 Correct 66 ms 3156 KB Output is correct
11 Correct 1655 ms 2640 KB Output is correct
12 Correct 67 ms 3012 KB Output is correct
13 Correct 74 ms 3152 KB Output is correct
14 Correct 64 ms 3296 KB Output is correct
15 Correct 87 ms 3408 KB Output is correct
16 Correct 63 ms 3156 KB Output is correct
17 Correct 28 ms 2644 KB Output is correct