oj.uz

Submission #883216

# Submission time Handle Problem Language Result Execution time Memory
883216 2023-12-04T19:42:42 Z Servant_of_the_Lord Mecho (IOI09_mecho) C++17
24 / 100
 1000 ms 65536 KB 
#include <bits/stdc++.h>
#define ll long long

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();
        }
        while(r.size())
        {
            
            for(ll i=0;i<y;i++)bear();
            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: 'long long int' and 'std::vector<std::vector<long long 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: 'long long int' and 'std::vector<std::vector<long long 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:91:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             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 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 536 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Runtime error 532 ms 65536 KB Execution killed with signal 9
8 Incorrect 1 ms 344 KB Output isn't correct
9 Correct 19 ms 7088 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Incorrect 2 ms 348 KB Output isn't correct
13 Runtime error 160 ms 65536 KB Execution killed with signal 9
14 Runtime error 103 ms 65536 KB Execution killed with signal 9
15 Correct 1 ms 344 KB Output is correct
16 Correct 4 ms 1012 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 24 ms 2684 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 163 ms 19280 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Runtime error 83 ms 65536 KB Execution killed with signal 9
23 Correct 2 ms 344 KB Output is correct
24 Runtime error 80 ms 65536 KB Execution killed with signal 9
25 Correct 2 ms 348 KB Output is correct
26 Runtime error 84 ms 65536 KB Execution killed with signal 9
27 Correct 2 ms 348 KB Output is correct
28 Runtime error 87 ms 65536 KB Execution killed with signal 9
29 Correct 3 ms 348 KB Output is correct
30 Runtime error 101 ms 65536 KB Execution killed with signal 9
31 Correct 4 ms 348 KB Output is correct
32 Runtime error 104 ms 65536 KB Execution killed with signal 9
33 Correct 81 ms 600 KB Output is correct
34 Runtime error 95 ms 65536 KB Execution killed with signal 9
35 Runtime error 136 ms 65536 KB Execution killed with signal 9
36 Correct 103 ms 708 KB Output is correct
37 Runtime error 104 ms 65536 KB Execution killed with signal 9
38 Runtime error 154 ms 65536 KB Execution killed with signal 9
39 Correct 130 ms 604 KB Output is correct
40 Runtime error 98 ms 65536 KB Execution killed with signal 9
41 Runtime error 166 ms 65536 KB Execution killed with signal 9
42 Correct 193 ms 832 KB Output is correct
43 Runtime error 109 ms 65536 KB Execution killed with signal 9
44 Runtime error 190 ms 65536 KB Execution killed with signal 9
45 Correct 218 ms 908 KB Output is correct
46 Runtime error 108 ms 65536 KB Execution killed with signal 9
47 Runtime error 218 ms 65536 KB Execution killed with signal 9
48 Correct 256 ms 1004 KB Output is correct
49 Runtime error 118 ms 65536 KB Execution killed with signal 9
50 Runtime error 304 ms 65536 KB Execution killed with signal 9
51 Correct 302 ms 856 KB Output is correct
52 Runtime error 139 ms 65536 KB Execution killed with signal 9
53 Runtime error 303 ms 65536 KB Execution killed with signal 9
54 Correct 351 ms 1116 KB Output is correct
55 Runtime error 130 ms 65536 KB Execution killed with signal 9
56 Runtime error 353 ms 65536 KB Execution killed with signal 9
57 Correct 402 ms 1116 KB Output is correct
58 Runtime error 130 ms 65536 KB Execution killed with signal 9
59 Runtime error 371 ms 65536 KB Execution killed with signal 9
60 Correct 468 ms 1372 KB Output is correct
61 Runtime error 144 ms 65536 KB Execution killed with signal 9
62 Runtime error 395 ms 65536 KB Execution killed with signal 9
63 Correct 749 ms 1456 KB Output is correct
64 Runtime error 384 ms 65536 KB Execution killed with signal 9
65 Execution timed out 1033 ms 1860 KB Time limit exceeded
66 Correct 998 ms 1460 KB Output is correct
67 Incorrect 803 ms 1472 KB Output isn't correct
68 Runtime error 534 ms 65536 KB Execution killed with signal 9
69 Runtime error 521 ms 65536 KB Execution killed with signal 9
70 Runtime error 599 ms 65536 KB Execution killed with signal 9
71 Execution timed out 1066 ms 21576 KB Time limit exceeded
72 Runtime error 493 ms 65536 KB Execution killed with signal 9
73 Runtime error 705 ms 65536 KB Execution killed with signal 9
74 Runtime error 550 ms 65536 KB Execution killed with signal 9
75 Runtime error 567 ms 65536 KB Execution killed with signal 9
76 Runtime error 631 ms 65536 KB Execution killed with signal 9
77 Runtime error 542 ms 65536 KB Execution killed with signal 9
78 Runtime error 561 ms 65536 KB Execution killed with signal 9
79 Runtime error 609 ms 65536 KB Execution killed with signal 9
80 Runtime error 545 ms 65536 KB Execution killed with signal 9
81 Runtime error 560 ms 65536 KB Execution killed with signal 9
82 Runtime error 592 ms 65536 KB Execution killed with signal 9
83 Runtime error 566 ms 65536 KB Execution killed with signal 9
84 Runtime error 548 ms 65536 KB Execution killed with signal 9
85 Runtime error 611 ms 65536 KB Execution killed with signal 9
86 Runtime error 552 ms 65536 KB Execution killed with signal 9
87 Runtime error 608 ms 65536 KB Execution killed with signal 9
88 Runtime error 541 ms 65536 KB Execution killed with signal 9
89 Runtime error 571 ms 65536 KB Execution killed with signal 9
90 Runtime error 544 ms 65536 KB Execution killed with signal 9
91 Runtime error 549 ms 65536 KB Execution killed with signal 9
92 Runtime error 540 ms 65536 KB Execution killed with signal 9