oj.uz

Submission #883231

# Submission time Handle Problem Language Result Execution time Memory
883231 2023-12-04T20:17:12 Z Servant_of_the_Lord Mecho (IOI09_mecho) C++17
24 / 100
 1000 ms 13624 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});
            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&&(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]==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();
            if(q.empty())break;
        }
        while(r.size())
        {
            
            for(ll i=0;i<y;i++)
            {
                bear();
                if(o)break;
            }
            if(o)break;
            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: 'short int' and 'std::vector<std::vector<short 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: 'short int' and 'std::vector<std::vector<short 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:97: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]
   97 |             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
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 404 KB Output is correct
6 Correct 0 ms 600 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 5 ms 2544 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Incorrect 2 ms 348 KB Output isn't correct
13 Incorrect 183 ms 9896 KB Output isn't correct
14 Incorrect 800 ms 13624 KB Output isn't correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 13 ms 2856 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 84 ms 9140 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Incorrect 299 ms 10144 KB Output isn't correct
23 Correct 2 ms 348 KB Output is correct
24 Incorrect 433 ms 9972 KB Output isn't correct
25 Correct 2 ms 348 KB Output is correct
26 Execution timed out 1083 ms 11624 KB Time limit exceeded
27 Correct 2 ms 600 KB Output is correct
28 Incorrect 700 ms 10952 KB Output isn't correct
29 Correct 2 ms 344 KB Output is correct
30 Incorrect 795 ms 9948 KB Output isn't correct
31 Correct 3 ms 344 KB Output is correct
32 Execution timed out 1090 ms 10928 KB Time limit exceeded
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 31 ms 604 KB Output isn't correct
37 Execution timed out 1049 ms 10084 KB Time limit exceeded
38 Execution timed out 1066 ms 11860 KB Time limit exceeded
39 Incorrect 8 ms 604 KB Output isn't correct
40 Execution timed out 1050 ms 10468 KB Time limit exceeded
41 Execution timed out 1031 ms 11960 KB Time limit exceeded
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 856 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 35 ms 860 KB Output isn't correct
49 Execution timed out 1077 ms 10552 KB Time limit exceeded
50 Execution timed out 1008 ms 12216 KB Time limit exceeded
51 Incorrect 32 ms 856 KB Output isn't correct
52 Execution timed out 1074 ms 11600 KB Time limit exceeded
53 Execution timed out 1041 ms 12332 KB Time limit exceeded
54 Incorrect 36 ms 1180 KB Output isn't correct
55 Execution timed out 1044 ms 11268 KB Time limit exceeded
56 Execution timed out 1061 ms 12408 KB Time limit exceeded
57 Incorrect 1 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 1116 KB Output isn't correct
62 Incorrect 2 ms 1116 KB Output isn't correct
63 Correct 2 ms 1116 KB Output is correct
64 Incorrect 3 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 Incorrect 2 ms 1112 KB Output isn't correct
68 Correct 2 ms 1116 KB Output is 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 Incorrect 2 ms 1116 KB Output isn't correct
79 Incorrect 3 ms 1116 KB Output isn't correct
80 Incorrect 2 ms 1116 KB Output isn't correct
81 Incorrect 2 ms 1272 KB Output isn't correct
82 Incorrect 2 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 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 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 2 ms 1116 KB Output isn't correct