Submission #442323

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442323	2021-07-07T12:51:15 Z	Haidara	Mecho (IOI09_mecho)	C++17	14 / 100	203 ms	65544 KB

mecho

/* * * * * * * * * *\
 * Author: Haidara *
 * LANG: C++17     *
 * PROB:           *
\* * * * * * * * * */
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define rep(i,x,n) for(int i=x;i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=x;i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define pq(i) priority_queue< i >
#define ff first
#define all(x) x.begin(),x.end()
#define ss second
#define pp push_back
using namespace std;
void SIO(string name="")
{
    if(name!="")
    {
        freopen((name+".in").c_str(),"r",stdin);
        freopen((name+".out").c_str(),"w",stdout);
    }
}
const int inf=1LL<<62LL;
const int mod=1e9+7;
const int maxn=808;
char a[maxn][maxn];
int n,jump;
pii M,D;
queue<pii>q;
int dist[maxn][maxn],dx[] {-1,1,0,0},dy[] {0,0,1,-1};
bool valid(int x,int y)
{
    return x>=0&&y>=0&&x<n&&y<n&&a[x][y]!='T';
}
void solve()
{
    while(q.size())
    {
        pii f=q.front();
        q.pop();
        FOR(i,4)
        {
            int x=f.ff+dx[i],y=f.ss+dy[i];
            if(valid(x,y)&&dist[f.ff][f.ss]+jump<dist[x][y])
                dist[x][y]=dist[f.ff][f.ss]+jump,q.push({x,y});
        }
    }
}
bool check(int st)
{
    queue<p(pii,int)>qq;
    qq.push({M,st*jump});
    bool ret=0;
    while(qq.size())
    {
        pii f=qq.front().ff;
        int curr=qq.front().ss;
        qq.pop();
        if(f.ff==D.ff&&D.ss==f.ss)
        {
            while(qq.size())
                qq.pop();
            return 1;
        }
        FOR(i,4)
        {
            int x=f.ff+dx[i],y=f.ss+dy[i];
            if(valid(x,y))
            {
                if(dist[x][y]>curr+1)
                    qq.push({{x,y},curr+1});
            }
        }
    }
    return 0;
}
signed main()
{
    SIO("");
    cin>>n>>jump;
    FOR(i,n)
    FOR(j,n)
    {
        dist[i][j]=inf;
        cin>>a[i][j];
        if(a[i][j]=='M')
            M= {i,j};
        else if(a[i][j]=='D')
            D= {i,j};
        else if(a[i][j]=='H')
            q.push({i,j}),dist[i][j]=0;
    }
    solve();
    int l=0,r=inf,ans=-1;
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        if(check(mid))
            ans=max(ans,mid),l=mid+1;
        else
            r=mid-1;
    }
    cout<<ans;
}

Compilation message

mecho.cpp: In function 'bool check(long long int)':
mecho.cpp:62:10: warning: unused variable 'ret' [-Wunused-variable]
   62 |     bool ret=0;
      |          ^~~
mecho.cpp: In function 'void SIO(std::string)':
mecho.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

14.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Incorrect	1 ms	332 KB	Output isn't correct
3	Correct	0 ms	204 KB	Output is correct
4	Incorrect	0 ms	204 KB	Output isn't correct
5	Correct	1 ms	588 KB	Output is correct
6	Runtime error	203 ms	65540 KB	Execution killed with signal 9
7	Runtime error	141 ms	65540 KB	Execution killed with signal 9
8	Correct	1 ms	332 KB	Output is correct
9	Runtime error	89 ms	65540 KB	Execution killed with signal 9
10	Correct	6 ms	1228 KB	Output is correct
11	Runtime error	87 ms	65540 KB	Execution killed with signal 9
12	Incorrect	1 ms	588 KB	Output isn't correct
13	Runtime error	92 ms	65540 KB	Execution killed with signal 9
14	Runtime error	87 ms	65540 KB	Execution killed with signal 9
15	Correct	0 ms	332 KB	Output is correct
16	Runtime error	122 ms	65540 KB	Execution killed with signal 9
17	Correct	1 ms	332 KB	Output is correct
18	Runtime error	119 ms	65540 KB	Execution killed with signal 9
19	Correct	1 ms	460 KB	Output is correct
20	Runtime error	119 ms	65540 KB	Execution killed with signal 9
21	Correct	1 ms	460 KB	Output is correct
22	Runtime error	122 ms	65540 KB	Execution killed with signal 9
23	Correct	1 ms	460 KB	Output is correct
24	Runtime error	115 ms	65540 KB	Execution killed with signal 9
25	Correct	1 ms	588 KB	Output is correct
26	Runtime error	125 ms	65540 KB	Execution killed with signal 9
27	Correct	1 ms	588 KB	Output is correct
28	Runtime error	139 ms	65540 KB	Execution killed with signal 9
29	Correct	1 ms	588 KB	Output is correct
30	Runtime error	119 ms	65540 KB	Execution killed with signal 9
31	Correct	1 ms	588 KB	Output is correct
32	Runtime error	127 ms	65540 KB	Execution killed with signal 9
33	Correct	10 ms	2784 KB	Output is correct
34	Runtime error	123 ms	65540 KB	Execution killed with signal 9
35	Runtime error	116 ms	65540 KB	Execution killed with signal 9
36	Correct	13 ms	3144 KB	Output is correct
37	Runtime error	128 ms	65540 KB	Execution killed with signal 9
38	Runtime error	118 ms	65536 KB	Execution killed with signal 9
39	Correct	16 ms	3404 KB	Output is correct
40	Runtime error	127 ms	65540 KB	Execution killed with signal 9
41	Runtime error	122 ms	65540 KB	Execution killed with signal 9
42	Correct	20 ms	3720 KB	Output is correct
43	Runtime error	134 ms	65540 KB	Execution killed with signal 9
44	Runtime error	127 ms	65540 KB	Execution killed with signal 9
45	Correct	25 ms	4172 KB	Output is correct
46	Runtime error	133 ms	65544 KB	Execution killed with signal 9
47	Runtime error	127 ms	65536 KB	Execution killed with signal 9
48	Correct	29 ms	4556 KB	Output is correct
49	Runtime error	145 ms	65540 KB	Execution killed with signal 9
50	Runtime error	131 ms	65540 KB	Execution killed with signal 9
51	Correct	33 ms	4912 KB	Output is correct
52	Runtime error	154 ms	65540 KB	Execution killed with signal 9
53	Runtime error	143 ms	65540 KB	Execution killed with signal 9
54	Correct	40 ms	5228 KB	Output is correct
55	Runtime error	150 ms	65540 KB	Execution killed with signal 9
56	Runtime error	150 ms	65540 KB	Execution killed with signal 9
57	Correct	43 ms	5572 KB	Output is correct
58	Runtime error	154 ms	65540 KB	Execution killed with signal 9
59	Runtime error	150 ms	65540 KB	Execution killed with signal 9
60	Correct	53 ms	5956 KB	Output is correct
61	Runtime error	159 ms	65540 KB	Execution killed with signal 9
62	Runtime error	157 ms	65540 KB	Execution killed with signal 9
63	Runtime error	166 ms	65540 KB	Execution killed with signal 9
64	Runtime error	165 ms	65540 KB	Execution killed with signal 9
65	Runtime error	165 ms	65540 KB	Execution killed with signal 9
66	Runtime error	168 ms	65540 KB	Execution killed with signal 9
67	Runtime error	175 ms	65540 KB	Execution killed with signal 9
68	Runtime error	168 ms	65536 KB	Execution killed with signal 9
69	Runtime error	169 ms	65540 KB	Execution killed with signal 9
70	Runtime error	170 ms	65540 KB	Execution killed with signal 9
71	Runtime error	170 ms	65540 KB	Execution killed with signal 9
72	Runtime error	168 ms	65540 KB	Execution killed with signal 9
73	Runtime error	139 ms	65540 KB	Execution killed with signal 9
74	Runtime error	143 ms	65540 KB	Execution killed with signal 9
75	Runtime error	143 ms	65540 KB	Execution killed with signal 9
76	Runtime error	143 ms	65536 KB	Execution killed with signal 9
77	Runtime error	144 ms	65540 KB	Execution killed with signal 9
78	Runtime error	147 ms	65536 KB	Execution killed with signal 9
79	Runtime error	139 ms	65540 KB	Execution killed with signal 9
80	Runtime error	139 ms	65540 KB	Execution killed with signal 9
81	Runtime error	151 ms	65540 KB	Execution killed with signal 9
82	Runtime error	141 ms	65536 KB	Execution killed with signal 9
83	Runtime error	137 ms	65540 KB	Execution killed with signal 9
84	Runtime error	139 ms	65540 KB	Execution killed with signal 9
85	Runtime error	142 ms	65540 KB	Execution killed with signal 9
86	Runtime error	141 ms	65540 KB	Execution killed with signal 9
87	Runtime error	139 ms	65540 KB	Execution killed with signal 9
88	Runtime error	143 ms	65536 KB	Execution killed with signal 9
89	Runtime error	138 ms	65540 KB	Execution killed with signal 9
90	Runtime error	139 ms	65540 KB	Execution killed with signal 9
91	Runtime error	140 ms	65540 KB	Execution killed with signal 9
92	Runtime error	142 ms	65540 KB	Execution killed with signal 9