oj.uz

Submission #884913

# Submission time Handle Problem Language Result Execution time Memory
884913 2023-12-08T16:37:39 Z TAFH Red-blue table (IZhO19_stones) C++17
100 / 100
 27 ms 2344 KB 
#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

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.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1612 KB Output is correct
2 Correct 23 ms 1884 KB Output is correct
3 Correct 24 ms 1884 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1360 KB Output is correct
2 Correct 22 ms 1620 KB Output is correct
3 Correct 19 ms 1368 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 27 ms 1612 KB Output is correct
6 Correct 23 ms 1884 KB Output is correct
7 Correct 24 ms 1884 KB Output is correct
8 Correct 25 ms 1360 KB Output is correct
9 Correct 22 ms 1620 KB Output is correct
10 Correct 19 ms 1368 KB Output is correct
11 Correct 8 ms 604 KB Output is correct
12 Correct 20 ms 1620 KB Output is correct
13 Correct 22 ms 1372 KB Output is correct
14 Correct 16 ms 1116 KB Output is correct
15 Correct 26 ms 2344 KB Output is correct
16 Correct 19 ms 1884 KB Output is correct
17 Correct 10 ms 1116 KB Output is correct