oj.uz

Submission #677684

# Submission time Handle Problem Language Result Execution time Memory
677684 2023-01-04T07:16:18 Z Alcabel Red-blue table (IZhO19_stones) C++17
100 / 100
 40 ms 2216 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> delta;

bool check(int a, int b) {
    int need = n / 2 + 1 - (n - a);
    if (need <= 0) { return true; }
    for (int i = 0, cur = 0; i < b; ++i) {
        if (cur + need <= a) {
            ++delta[cur];
            --delta[cur + need];
            cur += need;
        } else {
            ++delta[cur];
            --delta[a];
            ++delta[0];
            --delta[cur + need - a];
            cur = cur + need - a;
        }
    }
    bool able = true;
    for (int i = 0, cur = 0; i < a; ++i) {
        cur += delta[i];
        if (m - cur < m / 2 + 1) {
            able = false;
        }
        delta[i] = 0;
    }
    delta[a] = 0;
    return able;
}

void solve() {
    cin >> n >> m;
    pair<int, int> ans = {0, 0};
    delta.resize(n + 1);
    for (int a = 0; a <= n; ++a) {
        int left = 0, right = m + 1;
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (check(a, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (ans.first + ans.second < a + left) {
            ans.first = a, ans.second = left;
        }
    }
    cout << ans.first + ans.second << '\n';
    vector<vector<char>> t(n, vector<char>(m));
    for (int i = 0; i < ans.first; ++i) {
        for (int j = 0; j < m; ++j) {
            t[i][j] = '+';
        }
    }
    for (int i = ans.first; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            t[i][j] = '-';
        }
    }
    int need = n / 2 + 1 - (n - ans.first);
    if (need > 0) {
        for (int i = 0, cur = 0; i < ans.second; ++i) {
            for (int j = 0; j < need; ++j) {
                t[cur][i] = '-';
                ++cur;
                if (cur == ans.first) {
                    cur = 0;
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << t[i][j];
        }
        cout << '\n';
    }
}

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

    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 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 320 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1248 KB Output is correct
2 Correct 35 ms 1596 KB Output is correct
3 Correct 34 ms 1820 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1244 KB Output is correct
2 Correct 31 ms 1364 KB Output is correct
3 Correct 32 ms 1244 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 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 320 KB Output is correct
5 Correct 36 ms 1248 KB Output is correct
6 Correct 35 ms 1596 KB Output is correct
7 Correct 34 ms 1820 KB Output is correct
8 Correct 40 ms 1244 KB Output is correct
9 Correct 31 ms 1364 KB Output is correct
10 Correct 32 ms 1244 KB Output is correct
11 Correct 11 ms 552 KB Output is correct
12 Correct 34 ms 1468 KB Output is correct
13 Correct 34 ms 1236 KB Output is correct
14 Correct 23 ms 996 KB Output is correct
15 Correct 38 ms 2216 KB Output is correct
16 Correct 26 ms 1700 KB Output is correct
17 Correct 13 ms 920 KB Output is correct