oj.uz

Submission #158176

# Submission time Handle Problem Language Result Execution time Memory
158176 2019-10-15T08:37:21 Z koste4ka Red-blue table (IZhO19_stones) C++14
100 / 100
 78 ms 3436 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define pb push_back
#define F first
#define S second
#define lll long long
#define lld long double

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int N = 3e5 + 229;
const int M = 1e9 + 7;
const lll M2 = 1e9 + 9;
const lll mod = 998244353;
const int rx[8] = {1, 1, -1, -1, -2, -2, 2, 2};
const int ry[8] = {-2, 2, -2, 2, 1, -1, 1, -1};
const lld eps = 1e-7;
const double pi = acos(-1.0);

bool a[2000][2000];

int k[2000];

void solve() {
    int n, m;
    cin >> n >> m;
    int ans = max(n, m);
    for (int i = 0; i < max(n, m); ++i) {
        k[i] = 0;
    }
    vector < pair < int, int > > best;
    if (m > n) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                a[i][j] = 1;
            }
        }
        int now;
        for (int i = 0; i < n; ++i) {
            best.clear();
            best.shrink_to_fit();
            for (int j = 0; j < m; ++j) {
                if (k[j] + 1 >= (n + 1) / 2) {
                    continue;
                }
                best.pb({k[j], j});
            }
            sort(best.begin(), best.end());
            now = 0;
            for (auto j : best) {
                ++now;
                a[i][j.S] = 0;
                ++k[j.S];
                if (now >= m / 2 + 1) {
                    break;
                }
            }
            if (now >= m / 2 + 1) {
                ++ans;
            }
        }
    } else {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                a[i][j] = 0;
            }
        }
        int now;
       for (int j = 0; j < m; ++j) {
            best.clear();
            best.shrink_to_fit();
            for (int i = 0; i < n; ++i) {
                if (k[i] + 1 >= (m + 1) / 2) {
                    continue;
                }
                best.pb({k[i], i});
            }
            sort(best.begin(), best.end());
            now = 0;
            for (auto i : best) {
                ++now;
                a[i.S][j] = 1;
                ++k[i.S];
                if (now >= n / 2 + 1) {
                    break;
                }
            }
            if (now >= n / 2 + 1) {
                ++ans;
            }
        }
    }
    cout << ans << '\n';
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j]) {
                cout << '-';
            } else {
                cout << '+';
            }
        }
        cout << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 1628 KB Output is correct
2 Correct 71 ms 2680 KB Output is correct
3 Correct 64 ms 3040 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1656 KB Output is correct
2 Correct 61 ms 2560 KB Output is correct
3 Correct 57 ms 2168 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 66 ms 1628 KB Output is correct
6 Correct 71 ms 2680 KB Output is correct
7 Correct 64 ms 3040 KB Output is correct
8 Correct 63 ms 1656 KB Output is correct
9 Correct 61 ms 2560 KB Output is correct
10 Correct 57 ms 2168 KB Output is correct
11 Correct 18 ms 632 KB Output is correct
12 Correct 57 ms 2680 KB Output is correct
13 Correct 64 ms 2940 KB Output is correct
14 Correct 44 ms 2424 KB Output is correct
15 Correct 78 ms 3436 KB Output is correct
16 Correct 54 ms 2680 KB Output is correct
17 Correct 26 ms 2040 KB Output is correct