Submission #689860

#	Time	Username	Problem	Language	Result	Execution time	Memory
689860		KiriLL1ca	Red-blue table (IZhO19_stones)	C++17	17 / 100	225 ms	1416 KiB

stones

#include <bits/stdc++.h>
#define sz(x) (int)((x).size())
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fr first
#define sc second
#define pw(x) (1ll << x)
#define bcnt(x) (__builtin_popcountll(x))

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }

inline pair <int, vector <vector <char>>> calc (int n, int m) {
    set <pii> s;
    vector <vector <char>> a (n, vector <char> (m, '-'));
    for (int i = 0; i < m; ++i) s.insert({0, i});

    int nn = n / 2 + 1;
    int mm = m - m / 2 - 1;

    int ans = m;

    int uk = 0;
    while (sz(s) && uk < n) {
        int T = nn;
        while (T-- && sz(s)) {
            auto [c, id] = *s.begin(); s.erase(s.begin());
            a[uk][id] = '+';
            ++c;
            if (c < mm) s.insert({c, id});
        }
        ++uk; ans += !~T;
    }
    return {ans, a};
}

pair <int, vector <int>> bst;
int N, M;
inline int cost (vector <int> a) {
    int res = 0;
    for (int i = 0; i < N; ++i) {
        int s = 0;
        for (int j = 0; j < M; ++j) s += ((a[i] >> j & 1) ? +1 : -1);
        res += s > 0;
    }
    for (int i = 0; i < M; ++i) {
        int s = 0;
        for (int j = 0; j < N; ++j) s += ((a[j] >> i & 1) ? +1 : -1);
        res += s < 0;
    }
    return res;
}
inline void brute (int n, int m, vector <int> a) {
    if (!~n) return void(umax(bst, {cost(a), a}));
    for (int j = 0; j < pw(m); ++j) {
        a.pb(j); brute(n - 1, m, a);
        a.pop_back();
    }
}

inline void solve () {
    int n, m; cin >> n >> m;

    N = n, M = m;
    if (N <= 4 && M <= 4) {
        bst.fr = -1;
        brute(N, M, vector <int> ());
        cout << bst.fr << endl;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                cout << ((bst.sc[i] >> j & 1) ? '+' : '-');
            }
            cout << endl;
        }
        return;
    }



    auto ans1 = calc(n, m);
    auto ans2 = calc(m, n);

    if (ans1.fr > ans2.fr) {
        cout << m << endl;
        for (auto i : ans1.sc) {
            for (auto j : i) cout << j;
            cout << endl;
        }
    }
    else {
        cout << m << endl;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cout << (ans2.sc[j][i] == '+' ? '-' : '+');
            }
            cout << endl;
        }
    }
}

signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    int t = 1; cin >> t;
    while (t--) solve();
    return 0;
}

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