Submission #883220

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
883220	2023-12-04T19:47:17 Z	Servant_of_the_Lord	Mecho (IOI09_mecho)	C++17	24 / 100	1000 ms	65536 KB

mecho

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

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();
            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

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: 'long long int' and 'std::vector<std::vector<long long 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: 'long long int' and 'std::vector<std::vector<long long 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:92:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Runtime error	532 ms	65536 KB	Execution killed with signal 9
8	Incorrect	0 ms	348 KB	Output isn't correct
9	Correct	19 ms	8624 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Incorrect	2 ms	348 KB	Output isn't correct
13	Runtime error	176 ms	65536 KB	Execution killed with signal 9
14	Runtime error	94 ms	65536 KB	Execution killed with signal 9
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	604 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	21 ms	2788 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	167 ms	19576 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Runtime error	86 ms	65536 KB	Execution killed with signal 9
23	Correct	1 ms	344 KB	Output is correct
24	Runtime error	79 ms	65536 KB	Execution killed with signal 9
25	Correct	2 ms	348 KB	Output is correct
26	Runtime error	84 ms	65536 KB	Execution killed with signal 9
27	Correct	2 ms	348 KB	Output is correct
28	Runtime error	78 ms	65536 KB	Execution killed with signal 9
29	Correct	3 ms	344 KB	Output is correct
30	Runtime error	83 ms	65536 KB	Execution killed with signal 9
31	Correct	3 ms	348 KB	Output is correct
32	Runtime error	92 ms	65536 KB	Execution killed with signal 9
33	Correct	82 ms	672 KB	Output is correct
34	Runtime error	89 ms	65536 KB	Execution killed with signal 9
35	Runtime error	138 ms	65536 KB	Execution killed with signal 9
36	Correct	107 ms	600 KB	Output is correct
37	Runtime error	106 ms	65536 KB	Execution killed with signal 9
38	Runtime error	150 ms	65536 KB	Execution killed with signal 9
39	Correct	131 ms	768 KB	Output is correct
40	Runtime error	98 ms	65536 KB	Execution killed with signal 9
41	Runtime error	158 ms	65536 KB	Execution killed with signal 9
42	Correct	171 ms	600 KB	Output is correct
43	Runtime error	119 ms	65536 KB	Execution killed with signal 9
44	Runtime error	189 ms	65536 KB	Execution killed with signal 9
45	Correct	289 ms	856 KB	Output is correct
46	Runtime error	113 ms	65536 KB	Execution killed with signal 9
47	Runtime error	220 ms	65536 KB	Execution killed with signal 9
48	Correct	246 ms	860 KB	Output is correct
49	Runtime error	120 ms	65536 KB	Execution killed with signal 9
50	Runtime error	246 ms	65536 KB	Execution killed with signal 9
51	Correct	329 ms	1080 KB	Output is correct
52	Runtime error	125 ms	65536 KB	Execution killed with signal 9
53	Runtime error	268 ms	65536 KB	Execution killed with signal 9
54	Correct	370 ms	1116 KB	Output is correct
55	Runtime error	133 ms	65536 KB	Execution killed with signal 9
56	Runtime error	308 ms	65536 KB	Execution killed with signal 9
57	Correct	415 ms	1276 KB	Output is correct
58	Runtime error	130 ms	65536 KB	Execution killed with signal 9
59	Runtime error	351 ms	65536 KB	Execution killed with signal 9
60	Correct	479 ms	1368 KB	Output is correct
61	Runtime error	145 ms	65536 KB	Execution killed with signal 9
62	Runtime error	402 ms	65536 KB	Execution killed with signal 9
63	Correct	701 ms	1464 KB	Output is correct
64	Runtime error	371 ms	65536 KB	Execution killed with signal 9
65	Execution timed out	1039 ms	1880 KB	Time limit exceeded
66	Correct	954 ms	1500 KB	Output is correct
67	Incorrect	789 ms	1620 KB	Output isn't correct
68	Runtime error	513 ms	65536 KB	Execution killed with signal 9
69	Runtime error	505 ms	65536 KB	Execution killed with signal 9
70	Runtime error	568 ms	65536 KB	Execution killed with signal 9
71	Execution timed out	1063 ms	20860 KB	Time limit exceeded
72	Runtime error	483 ms	65536 KB	Execution killed with signal 9
73	Runtime error	724 ms	65536 KB	Execution killed with signal 9
74	Runtime error	573 ms	65536 KB	Execution killed with signal 9
75	Runtime error	541 ms	65536 KB	Execution killed with signal 9
76	Runtime error	599 ms	65536 KB	Execution killed with signal 9
77	Runtime error	555 ms	65536 KB	Execution killed with signal 9
78	Runtime error	529 ms	65536 KB	Execution killed with signal 9
79	Runtime error	543 ms	65536 KB	Execution killed with signal 9
80	Runtime error	545 ms	65536 KB	Execution killed with signal 9
81	Runtime error	588 ms	65536 KB	Execution killed with signal 9
82	Runtime error	550 ms	65536 KB	Execution killed with signal 9
83	Runtime error	553 ms	65536 KB	Execution killed with signal 9
84	Runtime error	535 ms	65536 KB	Execution killed with signal 9
85	Runtime error	602 ms	65536 KB	Execution killed with signal 9
86	Runtime error	585 ms	65536 KB	Execution killed with signal 9
87	Runtime error	536 ms	65536 KB	Execution killed with signal 9
88	Runtime error	583 ms	65536 KB	Execution killed with signal 9
89	Runtime error	590 ms	65536 KB	Execution killed with signal 9
90	Runtime error	531 ms	65536 KB	Execution killed with signal 9
91	Runtime error	537 ms	65536 KB	Execution killed with signal 9
92	Runtime error	524 ms	65536 KB	Execution killed with signal 9