Submission #1156399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156399		Faisal_Saqib	Red-blue table (IZhO19_stones)	C++20	26 / 100	23 ms	3084 KiB

stones

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxpq = priority_queue<T, vector<T>, less<T>>;

void input(vll&q)
{
    for(auto&i:q)cin>>i;
}
void pyn(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
void pYN(bool x)
{
    cout<<(x?"Yes":"No")<<endl;
}
void pAB(bool x)
{
    cout<<(x?"Alice":"Bob")<<endl;
}
// ll get_ans(ll n,ll m)
pair<ll,vector<string>> get_ans(ll n,ll m)
{
    ll r=(m/2)+1; // red in row
    ll b=(m-r); // blue in row
    ll tb=b*n; // total blue in grid
    ll bm=(n/2)+1; // blue req in a single column
    // cout<<b<<' '<<tb<<' '<<bm<<endl;
    // return (n+min(m,(tb/bm)));
    // we can do (n-1) + b +b if n%2==1
    vector<string> ans;
    string cur(m,'+');
    for(int j=0;j<(m-r);j++)cur[j]='-';
    for(int i=0;i<(bm);i++)
    {
        ans.pb(cur);
    }
    for(int j=0;j<(m-r);j++)cur[j]='+',cur[m-1-j]='-';
    for(int i=0;i<(n-bm);i++)
    {
        ans.pb(cur);
    }
    // return {n+b,ans};
    pair<ll,vector<string>> cpr;
    if(n%2==0) // n>=2
    {
        // (n/2) + min(m,(b*(n/2)))
        if(b>=2)
        {
            reverse(all(ans));
            ans.pop_back();
            ans.pop_back();
            for(int j=0;j<m;j++)cur[j]='-';
                ans.pb(cur);
                ans.pb(cur);
            cpr={n-2+b+b,ans};
        }
        else
        {
            cpr={n+b,ans};
            // return
        }
        // ll tp=(n/2)+min(m,(b*(n/2)));
        // if(tp>=cpr.first)
        // {
        //     ans.clear();
        //     for(int j=0;j<m;j++)cur[j]='-';
        //     for(int i=0;i<n/2;i++)
        //     {
        //         ans.pb(cur);
        //     }
        //     for(int j=0;j<m;j++)cur[j]='+';
        //     for(int j=0;j<(m-r);j++)cur[j]='-';
        //     int shift=0;
        //     for(int i=0;i<n/2;i++)
        //     {
        //         string tp;
        //         for(int j=0;j<m;j++)tp+=cur[(j+shift)%m];
        //         ans.pb(tp);
        //         shift+=(m-r);
        //     }
        //     cpr={tp,ans};
        // }
        // return cpr;
        // (n-2) + b +b
    }
    else //n>=1
    {
        if(b>=1)
        {
            reverse(all(ans));
            ans.pop_back();
            for(int j=0;j<m;j++)cur[j]='-';
                ans.pb(cur);
            cpr={n-1+b+b,ans};
        }
        else
        {
            cpr={n+b,ans};
            // return
        }
    }
    ll lvl=-1;
    if(n%2==0)lvl=n/2;
    else lvl=n-(n/2);
    ll tp=lvl+min(m,(b*lvl));
    if(tp>=cpr.first)
    {
        ans.clear();
        for(int j=0;j<m;j++)cur[j]='-';
        for(int i=0;i<n/2;i++)
        {
            ans.pb(cur);
        }
        for(int j=0;j<m;j++)cur[j]='+';
        for(int j=0;j<(m-r);j++)cur[j]='-';
        int shift=0;
        for(int i=0;i<lvl;i++)
        {
            string tp;
            for(int j=0;j<m;j++)tp+=cur[(j+shift)%m];
            ans.pb(tp);
            shift+=(m-r);
        }
        cpr={tp,ans};
    }
    if(n%2==0)
    {
        lvl=(n/2)-1;
        tp=(n-lvl)+min(m,((b*(n-lvl))/2));
        // cout<<b*(n-lvl)<<endl;
        // cout<<"Holy "<<lvl<<' '<<tp<<endl;
        if(tp>=cpr.first)
        {
            ans.clear();
            for(int j=0;j<m;j++)cur[j]='-';
            for(int i=0;i<lvl;i++)
            {
                ans.pb(cur);// only --------
            }
            for(int j=0;j<m;j++)cur[j]='+';
            for(int j=0;j<(m-r);j++)cur[j]='-';
            int shift=0;
            for(int i=0;i<n-lvl;i++)
            {
                string tp;
                for(int j=0;j<m;j++)tp+=cur[(j+shift)%m];
                ans.pb(tp);
                shift-=(m-r);
                shift=((shift%m)+m)%m;
            }
            cpr={tp,ans};
        }        
    }
    return cpr;
    // return (n+b);
}
/*
---++++
+++-+--
++++---
-------
-------
-------
ans:10
*/
/*
Playground
--++++
++--++
++++--
------
------
------
ans:9

++++++
++++++
------
------
------
------
ans:8

--++++
--++++
----++
----++
++--++
++--++
ans:8
*/
void solve()
{
    // problem with even
    ll n,m;
    cin>>n>>m;
    auto mx=get_ans(n,m);

    if(mx>=get_ans(m,n))
    {
        cout<<mx.first<<endl;
        for(auto j:mx.second)
        {
            cout<<j<<endl;
        }
        // string cur(m,'+');
        // for(int i=0;i<((m-1)/2);i++)
        //     cur[i]='-';
        // cout<<mx_pos(n,m)<<endl;
        // for(int i=0;i<n;i++)
        //     cout<<cur<<endl;
    }
    else
    {
        mx=get_ans(m,n);
        cout<<mx.first<<endl;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                char c=mx.second[j][i];
                cout<<((c=='+')?'-':'+');
            }
            cout<<endl;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
}

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