Submission #582708

#	Time	Username	Problem	Language	Result	Execution time	Memory
582708		Kanaifu	Gardening (RMI21_gardening)	C++17	100 / 100	65 ms	912 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pb push_back
#define fr first
#define sc second

map <pair<int,int>,int> arr;
int vreme;
ll n, m, k;
int color(pair<int,int> start, pair<int,int> kraj)
{
    if (kraj.fr <= start.fr or kraj.sc <= start.sc)
    {
        return 0;
    }
    vreme ++;
    for (int i=start.fr; i<=kraj.fr; i++)
    {
        arr[{i,start.sc}] = vreme;
        arr[{i,kraj.sc}] = vreme;
    }
    for (int j=start.sc; j<=kraj.sc; j++)
    {
        arr[{start.fr,j}] = vreme;
        arr[{kraj.fr,j}] = vreme;
    }
    return 1;
}

int normal(pair<int,int> start, pair<int,int> kraj)
{
    int ret = 0;
    for (int i=start.fr; i<kraj.fr; i+=2)
    {
        for (int j=start.sc; j<kraj.sc; j+=2)
        {
            ret++;
            vreme++;
            arr[{i,j}] = vreme;
            arr[{i+1,j}] = vreme;
            arr[{i,j+1}] = vreme;
            arr[{i+1,j+1}] = vreme;
        }
    }
    return ret;
}

bool solve_with_4_vertical (pair<int,int> start, pair<int,int> kraj, int req)
{
    //cout<<start.fr<<" "<<start.sc<< " "<<kraj.fr<<" "<<kraj.sc<<"\n";
    for (int i=start.fr-1; i<=kraj.fr; i+=2) /// i is horizontal direction
    {
        if (i-start.fr==1)
        {
            continue;
        }
        if (req == (kraj.fr-start.fr+1) -((i-start.fr+1)/2))
        {
            color({start.fr,start.sc}, {i, kraj.sc});
            normal({start.fr+1,start.sc+1}, {i-1,kraj.sc-1});
            normal({i+1, start.sc}, {kraj.fr, kraj.sc});
            return true;
        }
    }
    return false;
}


bool solve_with_4 (pair<int,int> start, pair<int,int> kraj, int req)
{
    //cout<<start.fr<<" "<<start.sc<< " "<<kraj.fr<<" "<<kraj.sc<<"\n";
    for (int i=start.sc-1; i<=kraj.sc; i+=2) /// i is horizontal direction
    {
        if (i-start.sc==1)
        {
            continue;
        }
        if (req == (kraj.sc-start.sc+1) -((i-start.sc+1)/2))
        {
            color({start.fr,start.sc}, {kraj.fr, i});
            normal({start.fr+1,start.sc+1}, {kraj.fr-1,i-1});
            normal({start.fr, i+1}, {kraj.fr, kraj.sc});
            return true;
        }
    }
    return false;
}

bool solve(pair<int,int> start, pair<int,int> kraj, int req)
{
    if (req<(kraj.sc-start.sc+1)/2 or req<(kraj.fr-start.fr+1)/2)
    {
        return false;
    }
    if (kraj.sc<=start.sc + 1 or kraj.fr<=start.fr + 1)
    {
        return false;
    }
    if (req == (kraj.fr - start.fr+1)*(kraj.sc-start.sc+1)/4)
    {
        normal({start.fr, start.sc},{kraj.fr, kraj.sc});
        return true;
    }
    else if (req > (kraj.fr - start.fr+1)*(kraj.sc-start.sc+1)/4)
    {
        return false;
    }
    if (kraj.fr - start.fr + 1== 4)
    {
        if (solve_with_4(start, kraj, req))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    if (kraj.sc - start.sc + 1 == 4)
    {
        if (solve_with_4_vertical(start, kraj, req))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    for (int i=start.fr + 3; i<=kraj.fr; i+=2)
    {
        for (int j=start.sc + 3; j<=kraj.sc; j+=2)
        {
            int plostina = (kraj.fr-start.fr+1)*(kraj.sc - start.sc+1) - (j+1-start.sc)*2 - (i-1-start.fr)*2;
            int plostina_in = (i-start.fr-1)*(j-start.sc-1);
            int plostina_out = plostina - plostina_in;
            int sq = 1 + plostina/4;
            if (sq == req)
            {
                color({start.fr, start.sc},{i, j});
                normal({start.fr+1, start.sc+1}, {i-1, j-1});
                normal({i+1, start.sc}, {kraj.fr, kraj.sc});
                normal({start.fr, j+1},{i, kraj.sc});
                return true;
            }

            if (sq == req + 2)
            {
                if ((i-start.fr-1)>2 and (j-start.sc-1)>2)
                {
                    req -= color({start.fr, start.sc},{i, j});
                    req -= normal({i+1, start.sc}, {kraj.fr, kraj.sc});
                    req -= normal({start.fr, j+1},{i, kraj.sc});
                    return solve({start.fr+1, start.sc+1}, {i-1, j-1}, req);
                }
            }
        }
    }
    color(start, kraj);
    return solve({start.fr+1, start.sc+1}, {kraj.fr-1, kraj.sc-1}, req -1);
}

int main()
{
    int t;
    cin>>t;
    while (t>0)
    {
        t--;
        vreme = 0;
        bool ok = false, swapped = false;
        cin>>n>>m>>k;
        if (n>m)
        {
            swap(n, m);
            swapped = true;
        }
        if (n%2 ==1 or m%2==1)
        {
            cout<<"NO\n";
            continue;
        }
        if (n*m/4 < k)
        {
            cout<<"NO\n";
            continue;
        }
        if (k==n*m/4)
        {
            normal({0,0},{n-1, m-1});
            ok = true;
        }
        else if (n==2)
        {
            if (k == m/2)
            {
                normal({0,0},{n-1,m-1});
                ok = true;
            }
        }
        else if (n==4)
        {
            if (solve_with_4({0, 0}, {n-1, m-1}, k))
            {
                ok = true;
            }
        }
        else
        {
            if (solve({0,0},{n-1,m-1},k))
            {
                ok = true;
            }
        }
        if (ok)
        {
            cout<<"YES\n";
            if (swapped)
            {
                for (int j =0; j<m; j++)
                {
                    for (int i=0; i<n; i++)
                    {
                        cout<<arr[{i,j}]<<" ";
                    }
                    cout<<"\n";
                }
            }
            else
            {
                for (int i =0; i<n; i++)
                {
                    for (int j=0; j<m; j++)
                    {
                        cout<<arr[{i,j}]<<" ";
                    }
                    cout<<"\n";
                }
            }
            continue;
        }
        else
        {
            cout<<"NO\n";
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'bool solve(std::pair<int, int>, std::pair<int, int>, int)':
Main.cpp:139:17: warning: unused variable 'plostina_out' [-Wunused-variable]
  139 |             int plostina_out = plostina - plostina_in;
      |                 ^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 39 / 39
• Subtask 6: 22 / 22