CSES - BAPC 2015

Submission details
Task:	Godzilla
Sender:	KnowYourArchitecture
Submission time:	2017-10-17 20:03:07 +0300
Language:	C++
Status:	READY
Result:	WRONG ANSWER

Test results
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 ...` view save

correct output
`1 2 2 21 0 ...` view save

user output
`1 2 2 21 0 ...` view save

Test 2

Verdict: ACCEPTED

input
`6 3 1000 ... ... ... ...` view save

correct output
`0 4 0 1 1 ...` view save

user output
`0 4 0 1 1 ...` view save

Test 3

Verdict: WRONG ANSWER

input
`5 83 83 ..R....R........R.RRR.R..........` view save

correct output
`0 8 0 1 1` view save

user output
`0 6 0 1 1` view save

Test 4

Verdict: WRONG ANSWER

input
`5 183 183 ..R...R.............R.....R.R....` view save

correct output
`15 5 30 16 0` view save

user output
`11 5 25 16 0` view save

Test 5

Verdict: WRONG ANSWER

input
`5 283 283 ........................RR.......` view save

correct output
`0 31 4 2 13` view save

user output
`0 25 2 2 12` view save

Test 6

Verdict: WRONG ANSWER

input
`5 383 383 R.R...R........R...........R.R...` view save

correct output
`5 2 68 6 14` view save

user output
`3 2 64 4 14` view save

Test 7

Verdict: ACCEPTED

input
`5 483 483 R.........R......................` view save

correct output
`1 2 7 20 2` view save

user output
`1 2 7 20 2` view save

Test 8

Verdict: WRONG ANSWER

input
`5 583 583 .R...R.....R........R.....R......` view save

correct output
`5 5 86 1 51` view save

user output
`5 5 86 1 49` view save

Test 9

Verdict: WRONG ANSWER

input
`5 683 683 R...............R...R...R........` view save

correct output
`24 136 18 4 12` view save

user output
`24 134 18 4 11` view save

Test 10

Verdict: WRONG ANSWER

input
`5 783 783 ..........R....R....R........R...` view save

correct output
`12 18 10 5 4` view save

user output
`9 3 10 3 4` view save

Test 11

Verdict: WRONG ANSWER

input
`5 883 883 ..RR.R........R.R................` view save

correct output
`33 68 58 29 26` view save

user output
`27 67 54 24 25` view save

Test 12

Verdict: ACCEPTED

input
`1 983 983 ...R.R.R.R.....R.R.R.R...R.......` view save

correct output
`21` view save

user output
`21` view save

Test 13

Verdict: ACCEPTED

input
`1 1000 1000 ..R...R..R......R..........R.....` view save

correct output
`23` view save

user output
`23` view save

Test 14

Verdict: TIME LIMIT EXCEEDED

input
`2 12 6 ....R.....R. .R........RG .RRRRRRRRRR. ...` view save

correct output
`2 0` view save

user output
(empty)

BAPC 2015

Godzilla

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Tasks

Submissions (KnowYourArchitecture)