Submission #883210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
883210	2023-12-04T19:26:03 Z	Servant_of_the_Lord	Mecho (IOI09_mecho)	C++17	5 / 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)
                {
                    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();
        }
        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:91: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]
   91 |             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

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Correct	0 ms	456 KB	Output is correct
4	Incorrect	0 ms	600 KB	Output isn't correct
5	Correct	1 ms	344 KB	Output is correct
6	Incorrect	1 ms	348 KB	Output isn't correct
7	Runtime error	549 ms	65536 KB	Execution killed with signal 9
8	Incorrect	1 ms	604 KB	Output isn't correct
9	Incorrect	13 ms	7252 KB	Output isn't correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	2 ms	600 KB	Output is correct
12	Incorrect	3 ms	452 KB	Output isn't correct
13	Runtime error	171 ms	65536 KB	Execution killed with signal 9
14	Runtime error	106 ms	65536 KB	Execution killed with signal 9
15	Incorrect	1 ms	348 KB	Output isn't correct
16	Incorrect	3 ms	724 KB	Output isn't correct
17	Incorrect	1 ms	348 KB	Output isn't correct
18	Incorrect	7 ms	1356 KB	Output isn't correct
19	Incorrect	1 ms	344 KB	Output isn't correct
20	Incorrect	125 ms	20272 KB	Output isn't correct
21	Incorrect	1 ms	348 KB	Output isn't correct
22	Runtime error	88 ms	65536 KB	Execution killed with signal 9
23	Incorrect	2 ms	456 KB	Output isn't correct
24	Runtime error	105 ms	65536 KB	Execution killed with signal 9
25	Incorrect	3 ms	348 KB	Output isn't correct
26	Runtime error	103 ms	65536 KB	Execution killed with signal 9
27	Incorrect	4 ms	460 KB	Output isn't correct
28	Runtime error	91 ms	65536 KB	Execution killed with signal 9
29	Incorrect	6 ms	344 KB	Output isn't correct
30	Runtime error	117 ms	65536 KB	Execution killed with signal 9
31	Incorrect	5 ms	500 KB	Output isn't correct
32	Runtime error	96 ms	65536 KB	Execution killed with signal 9
33	Incorrect	142 ms	856 KB	Output isn't correct
34	Runtime error	148 ms	65536 KB	Execution killed with signal 9
35	Runtime error	165 ms	65536 KB	Execution killed with signal 9
36	Incorrect	200 ms	940 KB	Output isn't correct
37	Runtime error	173 ms	65536 KB	Execution killed with signal 9
38	Runtime error	166 ms	65536 KB	Execution killed with signal 9
39	Incorrect	228 ms	1108 KB	Output isn't correct
40	Runtime error	192 ms	65536 KB	Execution killed with signal 9
41	Runtime error	326 ms	65536 KB	Execution killed with signal 9
42	Incorrect	264 ms	1164 KB	Output isn't correct
43	Runtime error	224 ms	65536 KB	Execution killed with signal 9
44	Runtime error	268 ms	65536 KB	Execution killed with signal 9
45	Incorrect	368 ms	1116 KB	Output isn't correct
46	Runtime error	334 ms	65536 KB	Execution killed with signal 9
47	Runtime error	335 ms	65536 KB	Execution killed with signal 9
48	Incorrect	432 ms	1504 KB	Output isn't correct
49	Runtime error	315 ms	65536 KB	Execution killed with signal 9
50	Runtime error	313 ms	65536 KB	Execution killed with signal 9
51	Incorrect	556 ms	1632 KB	Output isn't correct
52	Runtime error	356 ms	65536 KB	Execution killed with signal 9
53	Runtime error	346 ms	65536 KB	Execution killed with signal 9
54	Incorrect	590 ms	2140 KB	Output isn't correct
55	Runtime error	390 ms	65536 KB	Execution killed with signal 9
56	Runtime error	384 ms	65536 KB	Execution killed with signal 9
57	Incorrect	704 ms	1968 KB	Output isn't correct
58	Runtime error	474 ms	65536 KB	Execution killed with signal 9
59	Runtime error	462 ms	65536 KB	Execution killed with signal 9
60	Incorrect	738 ms	2136 KB	Output isn't correct
61	Runtime error	485 ms	65536 KB	Execution killed with signal 9
62	Runtime error	497 ms	65536 KB	Execution killed with signal 9
63	Correct	513 ms	2436 KB	Output is correct
64	Runtime error	474 ms	65536 KB	Execution killed with signal 9
65	Execution timed out	1043 ms	2332 KB	Time limit exceeded
66	Incorrect	460 ms	2392 KB	Output isn't correct
67	Incorrect	749 ms	2392 KB	Output isn't correct
68	Runtime error	618 ms	65536 KB	Execution killed with signal 9
69	Runtime error	647 ms	65536 KB	Execution killed with signal 9
70	Runtime error	671 ms	65536 KB	Execution killed with signal 9
71	Execution timed out	1064 ms	24344 KB	Time limit exceeded
72	Runtime error	700 ms	65536 KB	Execution killed with signal 9
73	Runtime error	671 ms	65536 KB	Execution killed with signal 9
74	Runtime error	559 ms	65536 KB	Execution killed with signal 9
75	Runtime error	534 ms	65536 KB	Execution killed with signal 9
76	Runtime error	583 ms	65536 KB	Execution killed with signal 9
77	Runtime error	536 ms	65536 KB	Execution killed with signal 9
78	Runtime error	522 ms	65536 KB	Execution killed with signal 9
79	Runtime error	520 ms	65536 KB	Execution killed with signal 9
80	Runtime error	524 ms	65536 KB	Execution killed with signal 9
81	Runtime error	539 ms	65536 KB	Execution killed with signal 9
82	Runtime error	531 ms	65536 KB	Execution killed with signal 9
83	Runtime error	565 ms	65536 KB	Execution killed with signal 9
84	Runtime error	531 ms	65536 KB	Execution killed with signal 9
85	Runtime error	563 ms	65536 KB	Execution killed with signal 9
86	Runtime error	532 ms	65536 KB	Execution killed with signal 9
87	Runtime error	552 ms	65536 KB	Execution killed with signal 9
88	Runtime error	518 ms	65536 KB	Execution killed with signal 9
89	Runtime error	545 ms	65536 KB	Execution killed with signal 9
90	Runtime error	517 ms	65536 KB	Execution killed with signal 9
91	Runtime error	529 ms	65536 KB	Execution killed with signal 9
92	Runtime error	519 ms	65536 KB	Execution killed with signal 9