oj.uz

Submission #883246

# Submission time Handle Problem Language Result Execution time Memory
883246 2023-12-04T21:31:22 Z Servant_of_the_Lord Mecho (IOI09_mecho) C++17
46 / 100
 212 ms 1556 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;
    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')a=i,b=j;
            if(v[i][j]=='H')w.push_back({i,j});
        }
    }
    
    ll l=-1,h=x*x;
    while(l<h)
    {
        ll m=l+(h-l+1)/2;
        vector<string>u;
        for(string i:v)u.push_back(i);
        queue<vector<ll>>q,r;
        for(vector<ll>i:w)q.push(i);
        r.push({a,b});
        q.push({-1,-1});
        r.push({-1,-1});
        bool o=false;
        function<void(ll,ll)>a1=[&](ll a,ll b)
        {
            if(a<0||a>=x||b<0||b>=x||u[a][b]=='H'||u[a][b]=='D'||u[a][b]=='T')return;
            u[a][b]='H';
            q.push({a,b});
        };
        function<void(ll,ll)>a2=[&](ll a,ll b)
        {
            if(a<0||a>=x||b<0||b>=x||u[a][b]=='H'||u[a][b]=='M'||u[a][b]=='T')return;
            if(u[a][b]=='D')o=true;
            u[a][b]='M';
            r.push({a,b});
        };
        for(ll i=0;i<m;i++)
        {
            while(q.front()[0]!=-1)
            {
                a1(q.front()[0]-1,q.front()[1]);
                a1(q.front()[0]+1,q.front()[1]);
                a1(q.front()[0],q.front()[1]-1);
                a1(q.front()[0],q.front()[1]+1);
                q.pop();
            }
            q.pop();
            q.push({-1,-1});
        }
        while(r.front()[0]!=-1)
        {
            for(ll i=0;i<y;i++)
            {
                while(r.front()[0]!=-1)
                {
                    if(u[r.front()[0]][r.front()[1]]!='M')
                    {
                        r.pop();
                        continue;
                    }
                    a2(r.front()[0]-1,r.front()[1]);
                    a2(r.front()[0]+1,r.front()[1]);
                    a2(r.front()[0],r.front()[1]-1);
                    a2(r.front()[0],r.front()[1]+1);
                    r.pop();
                }
                r.pop();
                r.push({-1,-1});
            }
            while(q.front()[0]!=-1)
            {
                a1(q.front()[0]-1,q.front()[1]);
                a1(q.front()[0]+1,q.front()[1]);
                a1(q.front()[0],q.front()[1]-1);
                a1(q.front()[0],q.front()[1]+1);
                q.pop();
            }
            q.pop();
            q.push({-1,-1});
        }
        if(o)l=m;
        else h=m-1;
    }
    cout<<l<<'\n';
}

Compilation message

mecho.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main()
      | ^~~~
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;
      |                      ^
mecho.cpp:35:21: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |         r.push({a,b});
      |                     ^
mecho.cpp:35:21: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 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 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 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 2 ms 348 KB Output is correct
30 Correct 2 ms 344 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 2 ms 348 KB Output is correct
33 Incorrect 1 ms 600 KB Output isn't correct
34 Incorrect 1 ms 600 KB Output isn't correct
35 Incorrect 0 ms 348 KB Output isn't correct
36 Incorrect 64 ms 800 KB Output isn't correct
37 Incorrect 53 ms 804 KB Output isn't correct
38 Correct 65 ms 856 KB Output is correct
39 Incorrect 74 ms 892 KB Output isn't correct
40 Incorrect 59 ms 860 KB Output isn't correct
41 Correct 67 ms 920 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 1 ms 604 KB Output isn't correct
48 Incorrect 168 ms 1260 KB Output isn't correct
49 Incorrect 119 ms 1240 KB Output isn't correct
50 Correct 150 ms 1112 KB Output is correct
51 Incorrect 180 ms 1368 KB Output isn't correct
52 Incorrect 141 ms 1372 KB Output isn't correct
53 Correct 178 ms 1428 KB Output is correct
54 Incorrect 202 ms 1500 KB Output isn't correct
55 Incorrect 165 ms 1508 KB Output isn't correct
56 Correct 212 ms 1556 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 2 ms 1040 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 2 ms 1116 KB Output isn't correct
64 Incorrect 2 ms 964 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 1116 KB Output isn't correct
69 Incorrect 2 ms 940 KB Output isn't correct
70 Incorrect 3 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 1056 KB Output isn't correct
74 Incorrect 2 ms 1116 KB Output isn't correct
75 Incorrect 2 ms 1188 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 1112 KB Output is correct
79 Incorrect 2 ms 1116 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 3 ms 1116 KB Output isn't correct
83 Incorrect 3 ms 1116 KB Output isn't correct
84 Incorrect 2 ms 1112 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 1368 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