QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344121#7785. Three RectanglesQHJ123456WA 1ms3676kbC++172.5kb2024-03-03 16:34:072024-03-06 22:08:13

Judging History

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

  • [2024-03-06 22:08:13]
  • 管理员手动重测该提交记录
  • 测评结果:WA
  • 用时:1ms
  • 内存:3676kb
  • [2024-03-03 16:34:07]
  • 提交

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;
	}
	
	if (full>=0){
		int 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;
		int ans=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 = (ans+(W-w-1))%MOD;
					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 z=0; z<2; ++z){
		trans();
		for (int i=0; i<3; ++i) if (rect[i].ft==H){
	//		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){
					return freedom(k)*2%MOD;
				}else return 0;	
			}
		}
	}
	
	for (int z=0; z<2; ++z){
		trans();
		for (int i=0; i<3; ++i) if (rect[i].ft==H){
			if (rect[(i+1)%3].ft+rect[(i+2)%3].ft>=H && min(rect[(i+1)%3].sd, rect[(i+2)%3].sd)+rect[i].sd>=W){
				return 4;
			}
		}
	}
	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: 3616kb

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: 1ms
memory: 3616kb

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: 1ms
memory: 3676kb

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: 3664kb

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
814814847
0
0
0
6
382716043
382716043
382716043
246913568
493827185
0
0
6
382716043
382716043
382716043
382716043
24691346
172839523
0
6
382716043
382716043
382716043
382716043
3827160...

result:

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