QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#283032 | #7785. Three Rectangles | Loging# | WA | 0ms | 1616kb | C++20 | 1.9kb | 2023-12-13 18:26:26 | 2023-12-13 18:26:27 |
Judging History
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'