QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602313#7785. Three RectanglesAlphaZeTL 0ms0kbC++147.7kb2024-09-30 22:46:482024-09-30 22:47:34

Judging History

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

  • [2024-09-30 22:47:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-09-30 22:46:48]
  • 提交

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

output:


result: