Submission #677684

#	Time	Username	Problem	Language	Result	Execution time	Memory
677684		Alcabel	Red-blue table (IZhO19_stones)	C++17	100 / 100	40 ms	2216 KiB

stones

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