oj.uz

Submission #156394

# Submission time Handle Problem Language Result Execution time Memory
156394 2019-10-05T12:14:41 Z ASDF123 Red-blue table (IZhO19_stones) C++14
100 / 100
 33 ms 2336 KB 
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int, int>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
#define szof(s) (int)s.size()
#define Ok puts("Ok")
using namespace std;

const int N = (int)1e3 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = (int)1e9 + 9;

int tests = 1;
int n, m, ans;
char a[N][N], c[N][N];
vector <pair<int, int>> row, col;

void init() {
  row.clear();
  col.clear();
  ans = 0;
}


inline void solve() {
  init();
  cin >> n >> m;

  if (m >= n) {
    ans = m;
    int can = n - (n / 2 + 1);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        c[i][j] = '-';
      }
    }

    for (int j = 1; j <= m; j++) {
      col.push_back({j, can});
    }

    int need = m / 2 + 1;
    for (int i = 1; i <= n; i++) {
      if (col.empty() || col.size() < need) {
        break;
      }
      int cnt = 0;
      sort (all(col), [&](pii A, pii B) {
          return A.sc > B.sc;
        });
      for (int j = 0; j < need; j++) {
        if (col[j].sc) {
          cnt++;
        }
      }
      if (cnt == need) {
        ans++;
        for (int j = 0; j < need; j++) {
          c[i][col[j].fr] = '+';
          col[j].sc--;
        }
      } else {
        break;
      }

      while (!col.empty() && col.back().sc == 0) {
        col.pop_back();
      }
    }
  }
  else {
    ans = n;
    int can = m - (m / 2 + 1);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        c[i][j] = '+';
      }
    }

    for (int i = 1; i <= n; i++) {
      row.push_back({i, can});
    }

    int need = n / 2 + 1;
    for (int j = 1; j <= m; j++) {
      if (row.empty() || row.size() < need) {
        break;
      }

      int cnt = 0;
      sort (all(row), [&](pii A, pii B) {
        return A.sc > B.sc;
      });
      for (int i = 0; i < need; i++) {
        if (row[i].sc) {
          cnt++;
        }
      }
      if (cnt == need) {
        ans++;
        for (int i = 0; i < need; i++) {
          c[row[i].fr][j] = '-';
          row[i].sc--;
        }
      } else {
        break;
      }

      while (!row.empty() && row.back().sc == 0) {
        row.pop_back();
      }
    }
  }

  printf("%d\n", ans);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      putchar(c[i][j]);
    }printf("\n");
  }
}

main() {
  cin >> tests;
  while (tests--) {
    solve();
  }
}

Compilation message

stones.cpp: In function 'void solve()':
stones.cpp:46:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (col.empty() || col.size() < need) {
                          ~~~~~~~~~~~^~~~~~
stones.cpp:88:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (row.empty() || row.size() < need) {
                          ~~~~~~~~~~~^~~~~~
stones.cpp: At global scope:
stones.cpp:125:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1404 KB Output is correct
2 Correct 30 ms 2044 KB Output is correct
3 Correct 31 ms 2168 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1400 KB Output is correct
2 Correct 28 ms 1912 KB Output is correct
3 Correct 25 ms 1748 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 32 ms 1404 KB Output is correct
6 Correct 30 ms 2044 KB Output is correct
7 Correct 31 ms 2168 KB Output is correct
8 Correct 30 ms 1400 KB Output is correct
9 Correct 28 ms 1912 KB Output is correct
10 Correct 25 ms 1748 KB Output is correct
11 Correct 12 ms 524 KB Output is correct
12 Correct 28 ms 1912 KB Output is correct
13 Correct 29 ms 2040 KB Output is correct
14 Correct 23 ms 1656 KB Output is correct
15 Correct 33 ms 2336 KB Output is correct
16 Correct 25 ms 1784 KB Output is correct
17 Correct 13 ms 1272 KB Output is correct