QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344096#7785. Three RectanglesQHJ123456WA 1ms3732kbC++172.4kb2024-03-03 16:01:502024-03-03 16:01:51

Judging History

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

  • [2024-03-03 16:01:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3732kb
  • [2024-03-03 16:01:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long

using pii = pair<int, int>;
#define ft first
#define sd second

const int MOD = (int)1e9+7;

int t;
pii rect[4];

void trans(){for (int i=0; i<4; ++i) swap(rect[i].ft, rect[i].sd);}
int freedom(int x){
	auto &[H, W]=rect[3];
	auto &[h, w]=rect[x];
	return (H-h+1)*(W-w+1)%MOD;
}

int solve(){
	cin >> rect[3].ft >> rect[3].sd;
	for (int i=0; i<3; ++i) cin >> rect[i].ft >> rect[i].sd;
	int full=-1;
	auto &[H, W] = rect[3];
	for (int i=0; i<3; ++i){
		if (rect[i].ft==H && rect[i].sd==W) full=i;
	}
	
	int ans=0;
	if (full>0){
		ans=1;
		for (int i=0; i<3; ++i) if (i!=full) ans=ans*freedom(i)%MOD;
		return ans;
	}
	
	for (int z=0; z<2; ++z){
		int cnt=0;
		trans();
		for (int i=0; i<3; ++i) if (rect[i].ft==H){++cnt;}
		if (3==cnt){
			if (rect[0].sd+rect[1].sd+rect[2].sd<W) return 0;
//			printf("11111\n");
			ans=0;
			for (int i=0; i<3; ++i){
				for (int j=0; j<3; ++j) if (i!=j){
					int k=0; while (k<3 && (k==i || k==j)) ++k;
					auto &[h, w] = rect[k];			
					if (rect[i].sd+rect[j].sd>=W) ans += (W-w-1);
					else{
						int w1=rect[i].sd, w2=W-rect[j].sd;
						int l1 = ((1+w)>=w2 ? 1 : w2-w);
						int r1 = ((w1+w)>=W ? W-w-1 : w1);
						int l2 = ((w2-w)>=1 ? w2 : 1+w);
						int r2 = ((W-w-1)<=w1 ? W-1 : w1+w);
//						printf("l1=%lld r1=%lld l2=%lld r2=%lld\n", l1, r1, l2, r2);
						ans =  (ans+(r1-l1+1)*(r2-l2+1)%MOD)%MOD;
					}
				}
				if (rect[i].sd+max(rect[(i+1)%3].sd, rect[(i+2)%3].sd) >= W) ans=(ans+2)%MOD;
			}
			return ans;
		}
	}
	

	for (int i=0; i<3; ++i) if (rect[i].ft==H || rect[i].sd==W){
		if (rect[i].ft!=H) trans();
//		printf("i=%lld\n", i);
//		printf("H=%lld W=%lld\n", H, W);
//		for (int x=0; x<4; ++x) printf("i=%lld (%lld %lld)\n", x, rect[x].ft, rect[x].sd);
		for (int j=0; j<3; ++j) if (j!=i && rect[j].ft==H){
			int k=0; while (k<3 && (k==i || k==j)) ++k;
//			printf("i=%lld j=%lld free(%lld)=%lld\n", i, j, k, freedom(k));
			if (rect[i].sd+rect[j].sd>=W){
				ans = (ans+freedom(k))%MOD;
				return ans*2%MOD;
			}else return 0;	
		}
//		printf("ok=%d ans=%lld\n", ok, ans);
		if (rect[(i+1)%3].ft+rect[(i+2)%3].ft>=H && min(rect[(i+1)%3].sd, rect[(i+2)%3].sd)+rect[3].sd>=W){
			ans=(ans+4)%MOD;
			return ans;
		}
	}
	return 0;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t;
	while (t--) cout << solve() << '\n';
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 0ms
memory: 3732kb

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:

6
12
14
6

result:

ok 4 number(s): "6 12 14 6"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

1
1000000000 1000000000
1 1
1 1
1000000000 1000000000

output:

2401

result:

ok 1 number(s): "2401"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3684kb

input:

729
999999999 111111111
111111111 111111111
111111111 111111111
111111111 111111111
999999999 111111111
111111111 111111111
222222222 111111111
111111111 111111111
999999999 111111111
111111111 111111111
111111111 111111111
333333333 111111111
999999999 111111111
111111111 111111111
444444444 111111...

output:

0
0
0
0
0
0
6
913580234
456790164
0
0
0
0
0
6
382716043
691358012
135802502
0
0
0
0
6
382716043
382716043
469135790
111111091
0
0
0
6
382716043
382716043
382716043
246913568
888888876
0
0
6
382716043
382716043
382716043
382716043
24691346
666666654
0
6
382716043
382716043
382716043
382716043
3827160...

result:

wrong answer 8th numbers differ - expected: '777777753', found: '913580234'