Task: | Godzilla |
Sender: | KnowYourArchitecture |
Submission time: | 2017-10-17 20:03:07 +0300 |
Language: | C++ |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.04 s | details |
#2 | ACCEPTED | 0.04 s | details |
#3 | WRONG ANSWER | 0.03 s | details |
#4 | WRONG ANSWER | 0.09 s | details |
#5 | WRONG ANSWER | 0.11 s | details |
#6 | WRONG ANSWER | 0.10 s | details |
#7 | ACCEPTED | 0.16 s | details |
#8 | WRONG ANSWER | 0.22 s | details |
#9 | WRONG ANSWER | 0.26 s | details |
#10 | WRONG ANSWER | 0.24 s | details |
#11 | WRONG ANSWER | 0.45 s | details |
#12 | ACCEPTED | 0.14 s | details |
#13 | ACCEPTED | 0.16 s | details |
#14 | TIME LIMIT EXCEEDED | -- | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:73:21: warning: 'Gy' may be used uninitialized in this function [-Wmaybe-uninitialized] if(lookup(Gy-1,Gx)=='R')--Gy,++r; ^ input/code.cpp:11:8: warning: 'Gx' may be used uninitialized in this function [-Wmaybe-uninitialized] if(x<0||y<0||x>=L||y>=W)return (char)0; ^
Code
#include <bits/stdc++.h> using namespace std; int main(){ int Tn; cin>>Tn; while(Tn--){ int L,W; cin>>L>>W; vector<string> g(W); auto lookup = [&](int y,int x){ if(x<0||y<0||x>=L||y>=W)return (char)0; else return g[y][x]; }; for(auto& it : g)cin>>it; queue<tuple<int,int>> qM; int Gx,Gy; vector<vector<int>> l(W); auto lookup_l = [&](int y,int x){ if(x<0||y<0||x>=L||y>=W)return 4; else return l[y][x]; }; for(auto& it : l)it.resize(L); int r=0; auto update_beams = [&](int i,int j){ if(lookup_l(i-1,j)&1||lookup_l(i+1,j)&1){ for(int k=i;k<W;++k){ if(lookup(k,j)=='R'||lookup_l(k,j)&1)break; l[k][j]|=1; } for(int k=i-1;k>=0;--k){ if(lookup(k,j)=='R'||lookup_l(k,j)&1)break; l[k][j]|=1; } } if(lookup_l(i,j-1)&2||lookup_l(i,j+1)&2){ for(int k=j;k<L;++k){ if(lookup(i,k)=='R'||lookup_l(i,k)&1)break; l[i][k]|=2; } for(int k=j-1;k>=0;--k){ if(lookup(i,k)=='R'||lookup_l(i,k)&1)break; l[i][k]|=2; } } }; auto cast_beam = [&](int i,int j){ for(int k=i;k<W;++k){ if(lookup(k,j)=='R'||lookup_l(k,j)&1)break; l[k][j]|=1; } for(int k=i-1;k>=0;--k){ if(lookup(k,j)=='R'||lookup_l(k,j)&1)break; l[k][j]|=1; } for(int k=j;k<L;++k){ if(lookup(i,k)=='R'||lookup_l(i,k)&2)break; l[i][k]|=2; } for(int k=j-1;k>=0;--k){ if(lookup(i,k)=='R'||lookup_l(i,k)&2)break; l[i][k]|=2; } }; for(int i=0;i<W;++i){ for(int j=0;j<L;++j){ if(lookup(i,j)=='M')qM.emplace(i,j),cast_beam(i,j),l[i][j]|=4; if(lookup(i,j)=='G')Gx=j,Gy=i; } } while(true){ if(lookup(Gy-1,Gx)=='R')--Gy,++r; else if(lookup(Gy,Gx+1)=='R')++Gx,++r; else if(lookup(Gy+1,Gx)=='R')++Gy,++r; else if(lookup(Gy,Gx-1)=='R')--Gx,++r; else if(lookup(Gy-1,Gx)!='G'&&lookup(Gy-1,Gx))--Gy; else if(lookup(Gy,Gx+1)!='G'&&lookup(Gy,Gx+1))++Gx; else if(lookup(Gy+1,Gx)!='G'&&lookup(Gy+1,Gx))++Gy; else if(lookup(Gy,Gx-1)!='G'&&lookup(Gy,Gx-1))--Gx; g[Gy][Gx]='G'; update_beams(Gy,Gx); int vv = qM.size(); while(--vv){ int i,j; tie(i,j) = qM.front();qM.pop(); if(~lookup_l(i+1,j)&4)cast_beam(i+1,j),l[i+1][j]|=4,qM.emplace(i+1,j); if(~lookup_l(i-1,j)&4)cast_beam(i-1,j),l[i-1][j]|=4,qM.emplace(i-1,j); if(~lookup_l(i,j+1)&4)cast_beam(i,j+1),l[i][j+1]|=4,qM.emplace(i,j+1); if(~lookup_l(i,j-1)&4)cast_beam(i,j-1),l[i][j-1]|=4,qM.emplace(i,j-1); } if(lookup_l(Gy,Gx))break; } cout<<r<<'\n'; } }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
6 3 3 RR. G.. M.R ... |
correct output |
---|
1 2 2 21 0 ... |
user output |
---|
1 2 2 21 0 ... |
Test 2
Verdict: ACCEPTED
input |
---|
6 3 1000 ... ... ... ... |
correct output |
---|
0 4 0 1 1 ... |
user output |
---|
0 4 0 1 1 ... |
Test 3
Verdict: WRONG ANSWER
input |
---|
5 83 83 ..R....R........R.RRR.R.......... |
correct output |
---|
0 8 0 1 1 |
user output |
---|
0 6 0 1 1 |
Test 4
Verdict: WRONG ANSWER
input |
---|
5 183 183 ..R...R.............R.....R.R.... |
correct output |
---|
15 5 30 16 0 |
user output |
---|
11 5 25 16 0 |
Test 5
Verdict: WRONG ANSWER
input |
---|
5 283 283 ........................RR....... |
correct output |
---|
0 31 4 2 13 |
user output |
---|
0 25 2 2 12 |
Test 6
Verdict: WRONG ANSWER
input |
---|
5 383 383 R.R...R........R...........R.R... |
correct output |
---|
5 2 68 6 14 |
user output |
---|
3 2 64 4 14 |
Test 7
Verdict: ACCEPTED
input |
---|
5 483 483 R.........R...................... |
correct output |
---|
1 2 7 20 2 |
user output |
---|
1 2 7 20 2 |
Test 8
Verdict: WRONG ANSWER
input |
---|
5 583 583 .R...R.....R........R.....R...... |
correct output |
---|
5 5 86 1 51 |
user output |
---|
5 5 86 1 49 |
Test 9
Verdict: WRONG ANSWER
input |
---|
5 683 683 R...............R...R...R........ |
correct output |
---|
24 136 18 4 12 |
user output |
---|
24 134 18 4 11 |
Test 10
Verdict: WRONG ANSWER
input |
---|
5 783 783 ..........R....R....R........R... |
correct output |
---|
12 18 10 5 4 |
user output |
---|
9 3 10 3 4 |
Test 11
Verdict: WRONG ANSWER
input |
---|
5 883 883 ..RR.R........R.R................ |
correct output |
---|
33 68 58 29 26 |
user output |
---|
27 67 54 24 25 |
Test 12
Verdict: ACCEPTED
input |
---|
1 983 983 ...R.R.R.R.....R.R.R.R...R....... |
correct output |
---|
21 |
user output |
---|
21 |
Test 13
Verdict: ACCEPTED
input |
---|
1 1000 1000 ..R...R..R......R..........R..... |
correct output |
---|
23 |
user output |
---|
23 |
Test 14
Verdict: TIME LIMIT EXCEEDED
input |
---|
2 12 6 ....R.....R. .R........RG .RRRRRRRRRR. ... |
correct output |
---|
2 0 |
user output |
---|
(empty) |