Submission #1156462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156462		Faisal_Saqib	Red-blue table (IZhO19_stones)	C++20	100 / 100	51 ms	4640 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;
}
int count(int n,int m,vector<string> g)
{
    int ans=0;
    for(int i=0;i<n;i++)
    {
        map<char,int> cnt;
        for(int j=0;j<m;j++)cnt[g[i][j]]++;
        ans+=(cnt['+']>cnt['-']);
    }    
    for(int j=0;j<m;j++)
    {
        map<char,int> cnt;
        for(int i=0;i<n;i++)
        {
            cnt[g[i][j]]++;
        }
        ans+=(cnt['-']>cnt['+']);
    }
    return ans;
}
// 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,'+');
    
    // {
    pair<ll,vector<string>> cpr={-100,{}};
        ll lvl=n;
        ll br=(n/2)+1;
        ll len=min(m,((b*(lvl))/br));
        // if(tp>cpr.first)
        // {
            // cout<<b*(n-lvl)<<endl;
            // cout<<"Holy "<<lvl<<' '<<tp<<endl;
            ans.clear();
            for(int j=0;j<m;j++)cur[j]='+';
            for(int j=0;j<(m-r);j++)cur[j]='-';
            int shift=0;
        // cout<<cur<<endl;
        // cout<<len<<endl;
        //     cout<<"Make sure"<<endl;
            while((int)(cur.size())>len)
            {
                cur.pop_back();
            }
            // cout<<"clear"<<endl;
            for(int i=0;i<n;i++)
            {
                if(len!=0)
                {
                    string tp;
                    for(int j=0;j<len;j++)tp+=cur[(j+shift)%len];
                    ans.pb(tp);
                // cout<<tp<<endl;
                    shift-=(m-r);
                    shift=((shift%len)+len)%len;
                }
                else{ans.pb("");}
                while(ans.back().size()<m)ans.back()+='+';
            }

            // cout<<endl;
            ll tp=count(n,m,ans);
            // cout<<"Answer "<<tp<<endl;
            if(tp>=cpr.first)
                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: 17 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 31 / 31