Submission #883231

#	Time	Username	Problem	Language	Result	Execution time	Memory
883231		Servant_of_the_Lord	Mecho (IOI09_mecho)	C++17	24 / 100	1090 ms	13624 KiB

mecho

#include <bits/stdc++.h>
#define ll short

using namespace std;

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

    ll x,y,z,a,b,c,d,e;
    cin>>x>>y;
    vector<string>v;
    vector<vector<ll>>w,u;
    for(ll i=0;i<x;i++)
    {
        string s;
        cin>>s;
        v.push_back(s);
        for(ll j=0;j<x;j++)
        {
            if(v[i][j]=='M')w.push_back({i,j});
            if(v[i][j]=='H')u.push_back({i,j});
            if(v[i][j]=='D')d=i,e=j;
            
        }
    }
    
    a=0,b=x*x;
    while(a<b)
    {
        ll m=a+(b-a+1)/2;
        bool o=false;
        vector<vector<ll>>q,r;
        vector<vector<bool>>t(x,vector<bool>(x)),s(x,vector<bool>(x));
        
        function<void()>bees=[&]()
        {
            vector<vector<ll>>q2;
            function<void(ll,ll)>ba=[&](ll a,ll b)
            {
                if(a>=0&&a<x&&b>=0&&b<x&&t[a][b]==false&&(v[a][b]=='G'||v[a][b]=='M'))
                {
                    q2.push_back({a,b});
                    t[a][b]=true;
                }
                
            };
            for(ll i=0;i<q.size();i++)
            {
                ba(q[i][0]-1,q[i][1]);
                ba(q[i][0]+1,q[i][1]);
                ba(q[i][0],q[i][1]-1);
                ba(q[i][0],q[i][1]+1);
            }
            q2.swap(q);
        };
        function<void()>bear=[&]()
        {
            vector<vector<ll>>r2;
            function<void(ll,ll)>ba=[&](ll a,ll b)
            {
                if(a>=0&&a<x&&b>=0&&b<x&&t[a][b]==false&&s[a][b]==false&&(v[a][b]=='G'||v[a][b]=='D'))
                {
                    r2.push_back({a,b});
                    if(a==d&&b==e)o=true;
                }
                
            };
            for(ll i=0;i<r.size();i++)
            {
                ba(r[i][0]-1,r[i][1]);
                ba(r[i][0]+1,r[i][1]);
                ba(r[i][0],r[i][1]-1);
                ba(r[i][0],r[i][1]+1);
            }
            r2.swap(r);
        };
        for(auto i:w)r.push_back(i);
        for(auto i:u)q.push_back(i);
        for(ll i=0;i<m;i++)
        {
            bees();
            if(q.empty())break;
        }
        while(r.size())
        {
            
            for(ll i=0;i<y;i++)
            {
                bear();
                if(o)break;
            }
            if(o)break;
            bees();
            vector<vector<ll>>r2;
            for(ll i=0;i<r.size();i++)
            {
                if(!t[r[i][0]][r[i][1]])
                {
                    r2.push_back(r[i]);
                    s[r[i][0]][r[i][1]]=true;
                }
            }
            r2.swap(r);

        }
        if(o)a=m;
        else b=m-1;
    }
    cout<<a<<'\n';
}

Compilation message (stderr)

mecho.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main()
      | ^~~~
mecho.cpp: In lambda function:
mecho.cpp:49:25: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<std::vector<short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(ll i=0;i<q.size();i++)
      |                        ~^~~~~~~~~
mecho.cpp: In lambda function:
mecho.cpp:70:25: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<std::vector<short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for(ll i=0;i<r.size();i++)
      |                        ~^~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:97:25: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<std::vector<short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for(ll i=0;i<r.size();i++)
      |                        ~^~~~~~~~~
mecho.cpp:11:12: warning: unused variable 'z' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c,d,e;
      |            ^
mecho.cpp:11:18: warning: unused variable 'c' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c,d,e;
      |                  ^

• Subtask 1: 24 / 100