QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#68838#5112. Where Am I?chenshi#TL 0ms0kbC++141.7kb2022-12-21 10:46:262022-12-21 10:46:29

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-21 10:46:29]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-12-21 10:46:26]
  • 提交

answer

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int o=1e6;
int n,m,dx[o],dy[o],cnt,ans1,ans2;char s[110][110];
struct State{int sx,sy,x,y;};
vector<State> bg1,bg2,Ans;
void slv(vector<State> vec,int t){
	if((int)vec.size()==1){
		ans1+=--t;
		if(t>ans2) ans2=t,Ans.clear();
		if(t==ans2) Ans.push_back(vec[0]);
		return;
	}
	for(int c1,c2;1;++t){
		c1=c2=0;
		for(int i=vec.size();i--;){
			vec[i].x+=dx[t];vec[i].y+=dy[t];
			if(vec[i].x>=1&&vec[i].x<=n&&vec[i].y>=1&&vec[i].y<=m&&s[vec[i].x][vec[i].y]=='X') ++c1;
			else ++c2;
		}
		if(c1&&c2){
			vector<State> v1,v2;
			v1.reserve(c1);v2.reserve(c2);
			for(int i=vec.size();i--;)
				if(vec[i].x>=1&&vec[i].x<=n&&vec[i].y>=1&&vec[i].y<=m&&s[vec[i].x][vec[i].y]=='X') v1.push_back(vec[i]);
				else v2.push_back(vec[i]);
			vec.clear();
			if(!v1.empty()) slv(v1,t+1);
			if(!v2.empty()) slv(v2,t+1);
			break;
		}
	}
}
inline bool cmp(State A,State B){if(A.sy^B.sy) return A.sy<B.sy;return A.sx<B.sx;}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<500;++i){
		for(int j=1;j<2*i;++j) dx[++cnt]=0,dy[cnt]=1;
		for(int j=1;j<2*i;++j) dx[++cnt]=1,dy[cnt]=0;
		for(int j=1;j<=2*i;++j) dx[++cnt]=0,dy[cnt]=-1;
		for(int j=1;j<=2*i;++j) dx[++cnt]=-1,dy[cnt]=0;
	}
	for(int j=1;j<=m;++j) for(int i=1;i<=n;++i)
		do s[i][m-j+1]=getchar();while(s[i][m-j+1]-'X'&&s[i][m-j+1]-'.');
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
		if(s[i][j]=='X') bg1.push_back((State){i,j,i,j});
		else bg2.push_back((State){i,j,i,j});
	slv(bg1,1);slv(bg2,1);
	printf("%.5lf\n%d\n",ans1*1.0/(n*m),ans2);
	sort(Ans.begin(),Ans.end(),cmp);
	for(int i=0,sz=Ans.size();i<sz;++i) printf("(%d,%d) ",Ans[i].sx,Ans[i].sy);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

1 1
X

output:


result: