QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283032#7785. Three RectanglesLoging#WA 0ms1616kbC++201.9kb2023-12-13 18:26:262023-12-13 18:26:27

Judging History

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

  • [2023-12-13 18:26:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:1616kb
  • [2023-12-13 18:26:26]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#define P 1000000007
using namespace std;
int A[4],B[4];
inline void Add(long long &x,long long y){
	x=(x+y)%P;
}
int sz;
struct Rec{
	int Lx,Rx,Ly,Ry;
	void Print(){
		printf("[%d %d][%d %d]\n",Lx,Rx,Ly,Ry);
	}
	long long Get_area(){
		if(Lx>Rx||Ly>Ry)return 0;
		return 1ll*(Rx-Lx+1)*(Ry-Ly+1);
	}
}W[15];
int n,m;
int cnt[105];
Rec Jiao(Rec a,Rec b){
	Rec res;
	res.Lx=max(a.Lx,b.Lx);
	res.Rx=min(a.Rx,b.Rx);
	res.Ly=max(a.Ly,b.Ly);
	res.Ry=min(a.Ry,b.Ry);
	return res;
}
long long dfs(int chs,int step){
	if(step==3){
//		for(int i=1;i<=3;i++)W[i].Print();
//		puts("");
		long long ck=0;
		for(int i=1;i<=chs;i++){
			if((i|chs)==chs){
				Rec S=(Rec){1,n,1,m};
				for(int j=0;j<3;j++){
					if((1<<j)&i){
						S=Jiao(S,W[j+1]);
					}
				}
				if(cnt[i]&1)ck+=S.Get_area();
				else ck-=S.Get_area();
			}
		}
//		printf("ck=%lld\n",ck);
		if(ck==1ll*n*m){
			long long res=1;
			for(int i=0;i<3;i++){
				if((1<<i)&chs)continue;
				res=1ll*res*1ll*max(0,n-A[i]-1)%P*max(0,m-B[i]-1)%P;
			}
//			printf("chs=%d\n",chs);
//			printf("res=%lld\n",res);
			return res;
		}else return 0;
	}
	if((1<<step)&chs){
		long long res=0;
		W[++sz]=(Rec){1,A[step],1,B[step]};
		Add(res,dfs(chs,step+1));
		if(A[step]!=n){
			W[sz]=(Rec){n-A[step]+1,n,1,B[step]};
			Add(res,dfs(chs,step+1));
		}
		if(B[step]!=m){
			W[sz]=(Rec){1,A[step],m-B[step]+1,m};
			Add(res,dfs(chs,step+1));
		}
		if(A[step]!=n&&B[step]!=m){
			W[sz]=(Rec){n-A[step]+1,n,m-B[step]+1,m};
			Add(res,dfs(chs,step+1));
		}
		sz--;
		return res;
	}else {
		return dfs(chs,step+1);
	}
	return 0;
}
int main(){
	for(int i=0;i<105;i++)cnt[i]=cnt[i>>1]+(i&1);
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<3;i++)scanf("%d%d",&A[i],&B[i]);
		long long ans=0;
		for(int chs=1;chs<8;chs++){
			Add(ans,dfs(chs,0));
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 1616kb

input:

5
2 2
1 1
1 1
1 1
2 2
1 1
1 2
1 2
2 2
1 1
1 2
2 1
2 2
1 2
1 2
1 2
2 2
1 2
1 2
2 1

output:

0
8
4
6
4

result:

ok 5 number(s): "0 8 4 6 4"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 1536kb

input:

4
1 3
1 1
1 2
1 3
1 4
1 1
1 2
1 3
1 5
1 1
1 2
1 3
1 6
1 1
1 2
1 3

output:

4
6
4
0

result:

wrong answer 1st numbers differ - expected: '6', found: '4'