Submission #884871

#TimeUsernameProblemLanguageResultExecution timeMemory
884871TAFHRed-blue table (IZhO19_stones)C++17
27 / 100
2047 ms500 KiB
#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);
}

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 (n * k % (m - m / 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);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if (n > m) {
                if (j < m / 2 + 1 - k) {
                    ans[i][j] = '+';
                }
                else {
                    if (cols[i] >= k || rows[j] >= d) {
                        ans[i][j] = '-';
                    }
                    else {
                        ans[i][j] = '+';
                        cols[i]++;
                        rows[j]++;
                    }
                }
            }
            else {
                if (i < n / 2 + 1 - k) {
                    ans[i][j] = '-';
                }
                else {
                    if (cols[i] >= d || rows[j] >= k) {
                        ans[i][j] = '+';
                    }
                    else {
                        ans[i][j] = '-';
                        cols[i]++;
                        rows[j]++;
                    }
                }
            }
        }
    }

    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:44:15: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |         if (n * k % (m - m / 2 - 1 + k) != 0) d++;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...