oj.uz

Submission #689863

# Submission time Handle Problem Language Result Execution time Memory
689863 2023-01-29T15:04:19 Z KiriLL1ca Red-blue table (IZhO19_stones) C++17
100 / 100
 134 ms 4316 KB 
#include <bits/stdc++.h>
#define sz(x) (int)((x).size())
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fr first
#define sc second
#define pw(x) (1ll << x)
#define bcnt(x) (__builtin_popcountll(x))

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }

inline pair <int, vector <vector <char>>> calc (int n, int m) {
    set <pii> s;
    vector <vector <char>> a (n, vector <char> (m, '-'));

    int nn = n - n / 2 - 1;
    int mm = m / 2 + 1;

    if (nn > 0) {
        for (int i = 0; i < m; ++i) {
            s.insert({0, i});
        }
    }

    int ans = m;

    int uk = 0;
    while (sz(s) && uk < n) {
        int T = mm;
        while (T-- && sz(s)) {
            auto [c, id] = *s.begin(); s.erase(s.begin());
            a[uk][id] = '+';
            ++c;
            if (c < nn) s.insert({c, id});
        }
        ++uk; ans += !~T;
    }
    return {ans, a};
}

inline void solve () {
    int n, m; cin >> n >> m;

    auto ans1 = calc(n, m);
    auto ans2 = calc(m, n);

    if (ans1.fr > ans2.fr) {
        cout << ans1.fr << endl;
        for (auto i : ans1.sc) {
            for (auto j : i) cout << j;
            cout << endl;
        }
    }
    else {
        cout << ans2.fr << endl;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cout << (ans2.sc[j][i] == '-' ? '+' : '-');
            }
            cout << endl;
        }
    }
}

signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    int t = 1; cin >> t;
    while (t--) solve();
    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 13 ms 392 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 1380 KB Output is correct
2 Correct 103 ms 2948 KB Output is correct
3 Correct 97 ms 3380 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1388 KB Output is correct
2 Correct 98 ms 2512 KB Output is correct
3 Correct 87 ms 1872 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 13 ms 392 KB Output is correct
5 Correct 134 ms 1380 KB Output is correct
6 Correct 103 ms 2948 KB Output is correct
7 Correct 97 ms 3380 KB Output is correct
8 Correct 131 ms 1388 KB Output is correct
9 Correct 98 ms 2512 KB Output is correct
10 Correct 87 ms 1872 KB Output is correct
11 Correct 39 ms 532 KB Output is correct
12 Correct 95 ms 2360 KB Output is correct
13 Correct 101 ms 1812 KB Output is correct
14 Correct 72 ms 1244 KB Output is correct
15 Correct 115 ms 4316 KB Output is correct
16 Correct 101 ms 3276 KB Output is correct
17 Correct 36 ms 1544 KB Output is correct