oj.uz

Submission #883235

# Submission time Handle Problem Language Result Execution time Memory
883235 2023-12-04T20:32:59 Z Servant_of_the_Lord Mecho (IOI09_mecho) C++17
38 / 100
 370 ms 1316 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=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]&&(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
38.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 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 Incorrect 0 ms 348 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Incorrect 4 ms 552 KB Output isn't correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 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 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 344 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 348 KB Output is correct
32 Correct 3 ms 344 KB Output is correct
33 Incorrect 1 ms 604 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 95 ms 704 KB Output isn't correct
37 Incorrect 81 ms 708 KB Output isn't correct
38 Correct 140 ms 776 KB Output is correct
39 Incorrect 103 ms 600 KB Output isn't correct
40 Incorrect 96 ms 772 KB Output isn't correct
41 Correct 144 ms 856 KB Output is correct
42 Incorrect 1 ms 604 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 1 ms 604 KB Output isn't correct
48 Incorrect 208 ms 1012 KB Output isn't correct
49 Incorrect 195 ms 1000 KB Output isn't correct
50 Correct 280 ms 1164 KB Output is correct
51 Incorrect 248 ms 1080 KB Output isn't correct
52 Incorrect 221 ms 1088 KB Output isn't correct
53 Correct 329 ms 1244 KB Output is correct
54 Incorrect 286 ms 1116 KB Output isn't correct
55 Incorrect 265 ms 1184 KB Output isn't correct
56 Correct 370 ms 1316 KB Output is correct
57 Incorrect 2 ms 856 KB Output isn't correct
58 Incorrect 3 ms 856 KB Output isn't correct
59 Incorrect 2 ms 856 KB Output isn't correct
60 Incorrect 2 ms 1280 KB Output isn't correct
61 Incorrect 2 ms 1112 KB Output isn't correct
62 Incorrect 2 ms 1112 KB Output isn't correct
63 Correct 2 ms 1112 KB Output is correct
64 Incorrect 2 ms 1116 KB Output isn't correct
65 Incorrect 2 ms 1116 KB Output isn't correct
66 Incorrect 3 ms 1116 KB Output isn't correct
67 Incorrect 2 ms 1116 KB Output isn't correct
68 Correct 3 ms 1116 KB Output is correct
69 Incorrect 3 ms 1116 KB Output isn't correct
70 Incorrect 3 ms 1112 KB Output isn't correct
71 Incorrect 3 ms 1112 KB Output isn't correct
72 Incorrect 2 ms 1116 KB Output isn't correct
73 Incorrect 2 ms 1116 KB Output isn't correct
74 Incorrect 2 ms 1116 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 3 ms 1116 KB Output isn't correct
78 Incorrect 3 ms 1116 KB Output isn't correct
79 Incorrect 2 ms 1112 KB Output isn't correct
80 Incorrect 2 ms 1112 KB Output isn't correct
81 Incorrect 2 ms 1116 KB Output isn't correct
82 Incorrect 3 ms 1116 KB Output isn't correct
83 Correct 2 ms 1116 KB Output is correct
84 Incorrect 2 ms 1116 KB Output isn't correct
85 Incorrect 2 ms 1132 KB Output isn't correct
86 Incorrect 2 ms 1116 KB Output isn't correct
87 Incorrect 2 ms 1116 KB Output isn't correct
88 Correct 2 ms 1116 KB Output is 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 3 ms 1176 KB Output isn't correct