Submission #884913

#	Time	Username	Problem	Language	Result	Execution time	Memory
884913		TAFH	Red-blue table (IZhO19_stones)	C++17	100 / 100	27 ms	2344 KiB

stones

#include <bits/stdc++.h>

#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mp make_pair
#define mt make_tuple
#define ull unsigned long long
#define ll long long
#define dl long double
#define forn(i, n) for(int i = 0; i < n; i++)
using namespace std;

bool check(int k, int n, int m) {
    if (k == 0) return true;
    int d = n * k / (m - m / 2 - 1 + k);
    if (n * k % (m - m / 2 - 1 + k) != 0) d++;
    return d <= (n - n / 2 - 1);
}

int lol(int i, int n) {
    return i % n;
}

bool check_idx(int i, int l, int r) {
    if (l == r) return false;
    if (l < r) {
        return l <= i && i < r;
    }
    else {
        return i < r || l <= i;
    }
}

void start() {
    int n, m;
    cin >> n >> m;

    int k;
    int l = 0, r = max(n, m);
    while(l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid, max(n, m), min(n, m)) && !check(mid + 1, max(n, m), min(n, m))) {
            k = mid;
            break;
        }

        if (check(mid, max(n, m), min(n, m))) {
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }

    int d = 0;
    if (k != 0) {
        d = max(n, m) * k / (min(m, n) - min(m, n) / 2 - 1 + k);
        if (max(n, m) * k % (min(m, n) - min(m, n) / 2 - 1 + k) != 0) d++;
    }

    char ans[n][m];
    int cols[n + 1];
    int rows[m + 1];

    fill(cols, cols + n + 1, 0);
    fill(rows, rows + n + 1, 0);

    if (n > m) {
        int idx = 0;
        for(int j = 0; j < m; j++) {
            for(int i = 0; i < n; i++) {
                if (j < m / 2 + 1 - k) {
                    ans[i][j] = '+';
                }
                else {
                    if (check_idx(i, idx, lol(idx + d, n))) {
                        ans[i][j] = '+';
                    }
                    else {
                        ans[i][j] = '-';
                    }
                }
            }
            if (j >= m / 2 + 1 - k)
                idx = lol(idx + d, n);
        }
    }
    else {
        int idx = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (i < n / 2 + 1 - k) {
                    ans[i][j] = '-';
                }
                else {
                    if (check_idx(j, idx, lol(idx + d, m))) {
                        ans[i][j] = '-';
                    }
                    else {
                        ans[i][j] = '+';
                    }
                }
            }
            if (i >= n / 2 + 1 - k)
                idx = lol(idx + d, m);
        }
    }

    cout << k + (min(n, m) - min(n, m) / 2 - 1) + max(n, m) << "\n";

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << ans[i][j];
        }
        cout << "\n";
    }
}

int main() {
    //SPEED;
    int t = 1;
    cin >> t;
    while(t--) {
        start();
    }
} 

Compilation message (stderr)

stones.cpp: In function 'void start()':
stones.cpp:56:23: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |         d = max(n, m) * k / (min(m, n) - min(m, n) / 2 - 1 + k);
      |             ~~~~~~~~~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 31 / 31