제출 #395957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395957		rama_pang	Red-blue table (IZhO19_stones)	C++17	100 / 100	188 ms	2264 KiB

stones

#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 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 31 / 31