oj.uz

Submission #883237

# Submission time Handle Problem Language Result Execution time Memory
883237 2023-12-04T20:39:05 Z Servant_of_the_Lord Mecho (IOI09_mecho) C++17
46 / 100
 359 ms 1368 KB 
#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});
        }
    }
    
    a=-1,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]&&(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]&&!s[a][b]&&(v[a][b]=='G'||v[a][b]=='D'))
                {
                    r2.push_back({a,b});
                    s[a][b]=true;
                    if(v[a][b]=='D')o=true;   
                }                
            };
            for(ll i=0;i<r.size();i++)
            {
                if(t[r[i][0]][r[i][1]])continue;
                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();            
        }
        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:47: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]
   47 |             for(ll i=0;i<q.size();i++)
      |                        ~^~~~~~~~~
mecho.cpp: In lambda function:
mecho.cpp:68: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]
   68 |             for(ll i=0;i<r.size();i++)
      |                        ~^~~~~~~~~
mecho.cpp: In function 'int main()':
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;
      |                  ^
mecho.cpp:11:20: warning: unused variable 'd' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c,d,e;
      |                    ^
mecho.cpp:11:22: warning: unused variable 'e' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c,d,e;
      |                      ^

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 2 ms 1116 KB Output isn't correct
8 Correct 0 ms 568 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 500 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 2 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 2 ms 348 KB Output is correct
27 Correct 2 ms 472 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 3 ms 348 KB Output is correct
30 Correct 3 ms 348 KB Output is correct
31 Correct 3 ms 356 KB Output is correct
32 Correct 3 ms 348 KB Output is correct
33 Incorrect 1 ms 348 KB Output isn't correct
34 Incorrect 1 ms 604 KB Output isn't correct
35 Incorrect 1 ms 348 KB Output isn't correct
36 Incorrect 92 ms 720 KB Output isn't correct
37 Incorrect 81 ms 604 KB Output isn't correct
38 Correct 115 ms 792 KB Output is correct
39 Incorrect 103 ms 772 KB Output isn't correct
40 Incorrect 95 ms 604 KB Output isn't correct
41 Correct 118 ms 856 KB Output is correct
42 Incorrect 1 ms 600 KB Output isn't correct
43 Incorrect 1 ms 604 KB Output isn't correct
44 Incorrect 1 ms 604 KB Output isn't correct
45 Incorrect 1 ms 604 KB Output isn't correct
46 Incorrect 1 ms 604 KB Output isn't correct
47 Incorrect 2 ms 604 KB Output isn't correct
48 Incorrect 211 ms 860 KB Output isn't correct
49 Incorrect 198 ms 856 KB Output isn't correct
50 Correct 268 ms 1148 KB Output is correct
51 Incorrect 261 ms 1080 KB Output isn't correct
52 Incorrect 226 ms 1080 KB Output isn't correct
53 Correct 346 ms 1116 KB Output is correct
54 Incorrect 288 ms 1164 KB Output isn't correct
55 Incorrect 285 ms 1116 KB Output isn't correct
56 Correct 359 ms 1116 KB Output is correct
57 Incorrect 2 ms 856 KB Output isn't correct
58 Incorrect 2 ms 856 KB Output isn't correct
59 Incorrect 1 ms 860 KB Output isn't correct
60 Incorrect 2 ms 1116 KB Output isn't correct
61 Incorrect 2 ms 1116 KB Output isn't correct
62 Incorrect 2 ms 1116 KB Output isn't correct
63 Incorrect 2 ms 1116 KB Output isn't correct
64 Incorrect 2 ms 1116 KB Output isn't correct
65 Incorrect 2 ms 1116 KB Output isn't correct
66 Incorrect 2 ms 1116 KB Output isn't correct
67 Correct 2 ms 1116 KB Output is correct
68 Incorrect 2 ms 1112 KB Output isn't correct
69 Incorrect 2 ms 1112 KB Output isn't correct
70 Incorrect 2 ms 1112 KB Output isn't correct
71 Incorrect 2 ms 1116 KB Output isn't correct
72 Incorrect 2 ms 1184 KB Output isn't correct
73 Incorrect 2 ms 1116 KB Output isn't correct
74 Incorrect 2 ms 1172 KB Output isn't correct
75 Incorrect 2 ms 1116 KB Output isn't correct
76 Incorrect 2 ms 1116 KB Output isn't correct
77 Incorrect 2 ms 1116 KB Output isn't correct
78 Correct 2 ms 1116 KB Output is correct
79 Incorrect 2 ms 1116 KB Output isn't correct
80 Incorrect 2 ms 1116 KB Output isn't correct
81 Incorrect 2 ms 1196 KB Output isn't correct
82 Incorrect 2 ms 1116 KB Output isn't correct
83 Incorrect 2 ms 1116 KB Output isn't correct
84 Incorrect 2 ms 1116 KB Output isn't correct
85 Incorrect 2 ms 1116 KB Output isn't correct
86 Incorrect 2 ms 1116 KB Output isn't correct
87 Incorrect 3 ms 1368 KB Output isn't correct
88 Incorrect 2 ms 1116 KB Output isn't correct
89 Incorrect 2 ms 1116 KB Output isn't correct
90 Incorrect 2 ms 1116 KB Output isn't correct
91 Incorrect 2 ms 1116 KB Output isn't correct
92 Incorrect 2 ms 1116 KB Output isn't correct