oj.uz

Submission #395957

# Submission time Handle Problem Language Result Execution time Memory
395957 2021-04-29T09:17:35 Z rama_pang Red-blue table (IZhO19_stones) C++17
100 / 100
 188 ms 2264 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int T;
  cin >> T;
  while (T--) {
    int N, M;
    cin >> N >> M;

    bool rot = false;
    if (N > M) {
      swap(N, M);
      rot = true;
    }

    int best_A = 0;
    int best_score = M;

    int cur_score = M;
    int needRed = M / 2 + 1;
    int needBlue = N / 2 + 1;

    set<pair<int, int>> col_state;
    for (int i = 0; i < M; i++) {
      col_state.emplace(N, i);
    }

    for (int A = 1; A <= N; A++) {
      // Place "needRed" red stone in A-th column
      // Greedily in column with highest or lowest number of blues.
      // Depending on situation.
      for (int rep = 0; rep < needRed; rep++) {
        auto st = *begin(col_state);
        auto et = *prev(end(col_state));
        if (st.first < needBlue) { // column already useless, will never contribute
          col_state.erase(st);
          st.first--;
          if (st.first > 0) {
            col_state.emplace(st);
          }
        } else if (et.first > needBlue) { // can safely use
          col_state.erase(et);
          et.first--;
          if (et.first > 0) {
            col_state.emplace(et);
          }
        } else {
          assert(st.first == needBlue);
          assert(et.first == needBlue);
          cur_score -= 1;
          col_state.erase(st);
          st.first--;
          if (st.first > 0) {
            col_state.emplace(st);
          }
        }
      }

      cur_score += 1;
      if (cur_score > best_score) {
        best_score = cur_score;
        best_A = A;
      }
    }

    col_state.clear();
    for (int i = 0; i < M; i++) {
      col_state.emplace(N, i);
    }

    vector<string> state(N, string(M, '-'));
    for (int A = 1; A <= best_A; A++) {
      for (int rep = 0; rep < needRed; rep++) {
        auto st = *begin(col_state);
        auto et = *prev(end(col_state));
        if (st.first < needBlue) { // column already useless, will never contribute
          col_state.erase(st);
          st.first--;
          if (st.first > 0) {
            state[A - 1][st.second] = '+';
            col_state.emplace(st);
          }
        } else if (et.first > needBlue) { // can safely use
          col_state.erase(et);
          et.first--;
          if (et.first > 0) {
            state[A - 1][et.second] = '+';
            col_state.emplace(et);
          }
        } else {
          assert(st.first == needBlue);
          assert(et.first == needBlue);
          col_state.erase(st);
          st.first--;
          if (st.first > 0) {
            state[A - 1][st.second] = '+';
            col_state.emplace(st);
          }
        }
      }
    }

    cout << best_score << '\n';
    if (!rot) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
          cout << state[i][j];
        }
        cout << '\n';
      }
    } else {
      for (int j = 0; j < M; j++) {
        for (int i = 0; i < N; i++) {
          cout << char(state[i][j] ^ '+' ^ '-');
        }
        cout << '\n';
      }
    }
  }
  return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 8 ms 356 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 1308 KB Output is correct
2 Correct 172 ms 1624 KB Output is correct
3 Correct 166 ms 1856 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 1344 KB Output is correct
2 Correct 160 ms 1456 KB Output is correct
3 Correct 135 ms 1312 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 8 ms 356 KB Output is correct
5 Correct 174 ms 1308 KB Output is correct
6 Correct 172 ms 1624 KB Output is correct
7 Correct 166 ms 1856 KB Output is correct
8 Correct 172 ms 1344 KB Output is correct
9 Correct 160 ms 1456 KB Output is correct
10 Correct 135 ms 1312 KB Output is correct
11 Correct 37 ms 496 KB Output is correct
12 Correct 144 ms 1456 KB Output is correct
13 Correct 151 ms 1412 KB Output is correct
14 Correct 114 ms 964 KB Output is correct
15 Correct 188 ms 2264 KB Output is correct
16 Correct 137 ms 1748 KB Output is correct
17 Correct 59 ms 968 KB Output is correct