Submission #147729

#	Time	Username	Problem	Language	Result	Execution time	Memory
147729		andrew	Red-blue table (IZhO19_stones)	C++17	100 / 100	161 ms	3420 KiB

stones

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

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

template <typename T> void vout(T s){cout << s << endl;exit(0);}

char a[1001][1001], ma[1001][1001];
ll ans, res;

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

    ll q;
    cin >> q;

    while(q--){
        ll n, m;
        cin >> n >> m;
        ans = 0;
        ll cstr = m / 2 + 1, cstl = n / 2 + 1;

        set <pll> st;

        vector <pll> V;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                a[i][j] = '+';
            }
            if(cstr != m)st.insert({m - cstr, i});
        }

        res = n;

        for(int j = 1; j <= m; j++){
            if(ll(st.size()) >= cstl){
                ll k = cstl;
                while(k--){
                    V.p_b(*--st.end());
                    V.back().fi--;
                    st.erase(--st.end());
                    a[V.back().se][j] = '-';
                }
                for(auto i : V){
                    if(i.fi == 0)continue;
                    st.insert(i);
                }
                res++;
                V.clear();
            }else break;
        }

        ans = res;

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)ma[i][j] = a[i][j];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                a[i][j] = '-';
            }
        }

        st.clear();

        for(int i = 1; i <= m; i++)if(cstl != n)st.insert({n - cstl, i});

        res = m;

        for(int i = 1; i <= n; i++){
            if(ll(st.size()) >= cstr){
                ll k = cstr;
                while(k--){
                    V.p_b(*--st.end());
                    V.back().fi--;
                    st.erase(--st.end());
                    a[i][V.back().se] = '+';
                }
                for(auto i : V){
                    if(i.fi == 0)continue;
                    st.insert(i);
                }
                res++;
                V.clear();
            }else break;
        }

        if(res > ans){
            for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)ma[i][j] = a[i][j];
            ans = res;
        }

        cout << ans << "\n";

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

    }

    return 0;
}

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