oj.uz

Submission #883245

# Submission time Handle Problem Language Result Execution time Memory
883245 2023-12-04T20:56:05 Z Servant_of_the_Lord Mecho (IOI09_mecho) C++17
46 / 100
 349 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'||v[a][b]=='H'))
                {
                    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&&!s[a][b]&&(v[a][b]=='G'||v[a][b]=='D'||v[a][b]=='M'))
                {
                    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 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 2 ms 1164 KB Output isn't correct
8 Correct 1 ms 348 KB Output is 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 344 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 4 ms 556 KB Output is correct
15 Correct 1 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 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 344 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 2 ms 344 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 348 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 348 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 348 KB Output isn't correct
35 Incorrect 1 ms 604 KB Output isn't correct
36 Incorrect 92 ms 704 KB Output isn't correct
37 Incorrect 92 ms 708 KB Output isn't correct
38 Correct 117 ms 780 KB Output is correct
39 Incorrect 100 ms 604 KB Output isn't correct
40 Incorrect 91 ms 768 KB Output isn't correct
41 Correct 115 ms 868 KB Output is correct
42 Incorrect 1 ms 600 KB Output isn't correct
43 Incorrect 1 ms 600 KB Output isn't correct
44 Incorrect 1 ms 604 KB Output isn't correct
45 Incorrect 2 ms 604 KB Output isn't correct
46 Incorrect 1 ms 600 KB Output isn't correct
47 Incorrect 1 ms 604 KB Output isn't correct
48 Incorrect 208 ms 860 KB Output isn't correct
49 Incorrect 193 ms 1020 KB Output isn't correct
50 Correct 306 ms 1172 KB Output is correct
51 Incorrect 241 ms 1084 KB Output isn't correct
52 Incorrect 223 ms 860 KB Output isn't correct
53 Correct 307 ms 1216 KB Output is correct
54 Incorrect 293 ms 1164 KB Output isn't correct
55 Incorrect 267 ms 1164 KB Output isn't correct
56 Correct 349 ms 1304 KB Output is correct
57 Incorrect 2 ms 860 KB Output isn't correct
58 Incorrect 2 ms 860 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 1112 KB Output isn't correct
62 Incorrect 2 ms 1116 KB Output isn't correct
63 Incorrect 3 ms 1116 KB Output isn't correct
64 Incorrect 3 ms 1028 KB Output isn't correct
65 Incorrect 2 ms 1104 KB Output isn't correct
66 Incorrect 2 ms 1368 KB Output isn't correct
67 Correct 2 ms 1008 KB Output is correct
68 Incorrect 2 ms 1116 KB Output isn't correct
69 Incorrect 2 ms 1116 KB Output isn't correct
70 Incorrect 2 ms 1116 KB Output isn't correct
71 Incorrect 2 ms 1116 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 2 ms 1116 KB Output isn't correct
78 Correct 2 ms 1116 KB Output is correct
79 Incorrect 2 ms 1112 KB Output isn't correct
80 Incorrect 3 ms 1116 KB Output isn't correct
81 Incorrect 2 ms 1116 KB Output isn't correct
82 Incorrect 2 ms 1112 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 2 ms 1116 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 1112 KB Output isn't correct
92 Incorrect 2 ms 1116 KB Output isn't correct