QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#602313 | #7785. Three Rectangles | AlphaZe | TL | 0ms | 0kb | C++14 | 7.7kb | 2024-09-30 22:46:48 | 2024-09-30 22:47:34 |
answer
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
const int mod = 1e9 + 7;
void MulMod(int &p, int k) { p = 1ll * p * k % mod; }
void AddMod(int &p, int k) { p = (p + k) % mod; }
int ans;
int A, B;
int a[3], b[3], s[3], p[3];
bool can[3][2];
bool chk() {
bool fl = 0;
for (int i = 0; i < 3; ++i)
fl |= a[i] == A && b[i] == B;
if (fl) {
ans = 1;
for (int i = 0; i < 3; ++i)
MulMod(ans, 1ll * (A - a[i] + 1) * (B - b[i] + 1) % mod);
}
return fl;
}
int chk2(int step, int U, int D, int L, int R) {
// printf("chk2(%d, %d, %d, %d, %d); \n", step, U, D, L, R);
if (step == 3) {
if (D - U <= 1 || R - L <= 1) return 1;
return 0;
}
if (s[step] == 1) return chk2(step + 1, max(U, a[step]), D, L, R);
else if (s[step] == 3) return chk2(step + 1, U, min(D, A + 1 - a[step]), L, R);
else if (s[step] == 2) return chk2(step + 1, U, D, max(L, b[step]), R);
else return chk2(step + 1, U, D, L, min(R, B + 1 - b[step]));
}
int calc2(int step, int U, int D, int L, int R, bool fl0, bool fl1) {
// printf("calc2(%d, %d, %d, %d, %d, %d, %d); \n", step, U, D, L, R, fl0, fl1);
if (step == 2) {
if (fl0 && fl1) {
int aa = D - U - 1, bb = R - L - 1;
if (aa <= a[p[step]] && bb <= b[p[step]]) return 1;
return 0;
} else if (fl1) {
if (D - U <= 1) return 1ll * (A - a[p[step]] + 1) * (B - b[p[step]] + 1) % mod;
else {
if (b[p[step]] != B) return 0;
else {
int aa = D - U - 1;
if (a[p[step]] < aa) return 0;
int res = a[p[step]] - aa + 1;
res = min(res, U + 1);
res = min(res, A + 1 - D + 1);
return res;
}
}
} else {
if (R - L <= 1) return 1ll * (A - a[p[step]] + 1) * (B - b[p[step]] + 1) % mod;
else {
if (a[p[step]] != A) return 0;
else {
int bb = R - L - 1;
if (b[p[step]] < bb) return 0;
int res = b[p[step]] - bb + 1;
res = min(res, L + 1);
res = min(res, B + 1 - R + 1);
return res;
}
}
}
}
if (s[p[step]] == 1) return calc2(step + 1, max(U, a[p[step]]), D, L, R, fl0, 1);
else if (s[p[step]] == 3) return calc2(step + 1, U, min(D, A + 1 - a[p[step]]), L, R, fl0, 1);
else if (s[p[step]] == 2) return calc2(step + 1, U, D, max(L, b[p[step]]), R, 1, fl1);
else return calc2(step + 1, U, D, L, min(R, B + 1 - b[p[step]]), 1, fl1);
}
int calc3() {
// puts("calc3()");
// for (int i = 0; i < 3; ++i) printf("%d ", p[i]); putchar('\n');
int res = 0;
if (s[p[0]] == 1 || s[p[0]] == 3) {
int aa = A - a[p[0]];
bool fl3 = b[p[1]] == B, fl4 = b[p[2]] == B;
bool fl1 = a[p[1]] >= aa && b[p[1]] == B, fl2 = a[p[2]] >= aa && b[p[2]] == B;
if (fl1 && fl2) {
AddMod(res, 1ll * (A - a[p[2]] + 1) * (B - b[p[2]] + 1) % mod);
AddMod(res, 1ll * (A - a[p[1]] + 1) * (B - b[p[1]] + 1) % mod);
AddMod(res, mod - 1);
} else if (fl1) {
AddMod(res, 1ll * (A - a[p[2]] + 1) * (B - b[p[2]] + 1) % mod);
if (fl3 && fl4) AddMod(res, mod - 1);
} else if (fl2) {
AddMod(res, 1ll * (A - a[p[1]] + 1) * (B - b[p[1]] + 1) % mod);
if (fl3 && fl4) AddMod(res, mod - 1);
}
if (fl3 && fl4) {
s[p[1]] = s[p[0]];
if (s[p[1]] > 2) s[p[1]] -= 2; else s[p[1]] += 2;
if (!fl1) AddMod(res, calc2(0, 0, A + 1, 0, B + 1, 0, 0));
swap(p[1], p[2]);
s[p[1]] = s[p[0]];
if (s[p[1]] > 2) s[p[1]] -= 2; else s[p[1]] += 2;
if (!fl2) AddMod(res, calc2(0, 0, A + 1, 0, B + 1, 0, 0));
swap(p[1], p[2]);
} else {
if (fl1 || fl2);
else if (a[p[1]] < aa || a[p[2]] < aa);
else if (b[p[1]] + b[p[2]] < B);
else AddMod(res, 2);
}
} else {
int bb = B - b[p[0]];
bool fl3 = a[p[1]] == A, fl4 = a[p[2]] == A;
bool fl1 = b[p[1]] >= bb && a[p[1]] == A, fl2 = b[p[2]] >= bb && a[p[2]] == A;
if (fl1 && fl2) {
AddMod(res, 1ll * (A - a[p[2]] + 1) * (B - b[p[2]] + 1) % mod);
AddMod(res, 1ll * (A - a[p[1]] + 1) * (B - b[p[1]] + 1) % mod);
AddMod(res, mod - 1);
} else if (fl1) {
AddMod(res, 1ll * (A - a[p[2]] + 1) * (B - b[p[2]] + 1) % mod);
if (fl3 && fl4) AddMod(res, mod - 1);
} else if (fl2) {
AddMod(res, 1ll * (A - a[p[1]] + 1) * (B - b[p[1]] + 1) % mod);
if (fl3 && fl4) AddMod(res, mod - 1);
}
if (fl3 && fl4) {
s[p[1]] = s[p[0]];
if (s[p[1]] > 2) s[p[1]] -= 2; else s[p[1]] += 2;
if (!fl1) AddMod(res, calc2(0, 0, A + 1, 0, B + 1, 0, 0));
swap(p[1], p[2]);
s[p[1]] = s[p[0]];
if (s[p[1]] > 2) s[p[1]] -= 2; else s[p[1]] += 2;
if (!fl2) AddMod(res, calc2(0, 0, A + 1, 0, B + 1, 0, 0));
swap(p[1], p[2]);
} else {
if (fl1 || fl2);
else if (b[p[1]] < bb || b[p[2]] < bb);
else if (a[p[1]] + a[p[2]] < A);
else AddMod(res, 2);
}
}
return res;
}
int calc() {
// for (int i = 0; i < 3; ++i) printf("%d ", s[i]); putchar('\n');
int cnt = 0, res = 0;
for (int i = 0; i < 3; ++i) cnt += s[i] != 0;
if (!cnt) return 0;
else if (cnt == 1) {
int nm = 0;
for (int i = 0; i < 3; ++i) {
if (!s[i]) p[++nm] = i;
else p[0] = i;
}
return calc3();
} else if (cnt == 2) {
int nm = -1;
for (int i = 0; i < 3; ++i) {
if (s[i]) p[++nm] = i;
else p[2] = i;
}
// printf("->"); for (int i = 0; i < 3; ++i) printf("%d ", p[i]); putchar('\n');
return mod - calc2(0, 0, A + 1, 0, B + 1, 0, 0);
} else {
return chk2(0, 0, A + 1, 0, B + 1);
}
}
void work() {
A = read(); B = read();
for (int i = 0; i < 3; ++i) {
a[i] = read(), b[i] = read();
can[i][0] = can[i][1] = 0;
}
ans = 0;
if (chk()) {
printf("%d\n", ans);
} else {
for (int i = 0; i < 3; ++i) {
can[i][1] = b[i] == B; // 上下放
can[i][0] = a[i] == A; // 左右放
}
for (int i = 0; i <= 4; ++i) {
if ((!i) || can[0][i & 1]) {
for (int j = 0; j <= 4; ++j) {
if ((!j) || can[1][j & 1]) {
for (int k = 0; k <= 4; ++k) {
if ((!k) || can[2][k & 1]) {
s[0] = i; s[1] = j; s[2] = k;
AddMod(ans, calc());
// printf("ans = %d; \n", ans);
}
}
}
}
}
}
printf("%d\n", ans);
}
}
int main() {
freopen("I.in", "r", stdin);
// freopen("I.out", "w", stdout);
int Tt = read();
while (Tt--) work();
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
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