QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#281396#7785. Three Rectanglesucup-team197#WA 1ms3852kbC++205.4kb2023-12-10 03:43:382023-12-10 03:43:38

Judging History

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

  • [2023-12-10 03:43:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3852kb
  • [2023-12-10 03:43:38]
  • 提交

answer

#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;

const ll MOD = 1e9 + 7;

ll ways(int H, int W, int h, int w) {
    return (ll)(H - h + 1) * (W - w + 1) % MOD;
}

bool check(int H, int W, vector<pii> cards, vector<pii> pos) {
    auto check_cov = [&](int x, int y) {
        if(x < 0 || x >= H || y < 0 || y >= W) return true;
        for(int i = 0; i < 3; i++) {
            if(pos[i].first <= x && x < pos[i].first + cards[i].first && pos[i].second <= y && y < pos[i].second + cards[i].second) {
                return true;
            }
        }
        return false;
    };

    auto check_around = [&](int x, int y) {
        return check_cov(x, y) && check_cov(x-1, y) && check_cov(x-1, y-1) && check_cov(x, y-1);
    };
    for(int i = 0; i < 3; i++) {
        if(!check_around(pos[i].first, pos[i].second)
            || !check_around(pos[i].first + cards[i].first, pos[i].second)
            || !check_around(pos[i].first, pos[i].second + cards[i].second)
            || !check_around(pos[i].first + cards[i].first, pos[i].second + cards[i].second)) {
            return false;
        }
    }
    return true;
}

void solve() {
    int H, W;
    cin >> H >> W;
    vpii cards(3);
    for(int i = 0; i < 3; i++) {
        int h, w;
        cin >> h >> w;
        cards[i] = {h, w};
    }
    int cov_h = 0;
    int cov_w = 0;
    int cov_all = 0;
    for(int i = 0; i < 3; i++) {
        bool ch = cards[i].first == H;
        bool cw = cards[i].second == W;
        if(ch) {
            cov_h++;
        }
        if(cw) {
            cov_w++;
        }
        if(ch && cw) {
            cov_all++;
        }
    }

    // cerr << cov_all << ' ' << cov_h << ' ' << cov_w << endl;

    if(cov_all >= 1) {
        ll ans = 1;
        for(int i = 0; i < 3; i++) {
            ans = (ans * ways(H, W, cards[i].first, cards[i].second)) % MOD;
        }
        cout << ans << endl;
        return;
    }

    if(cov_w >= 2) {
        swap(H, W);
        for(int i = 0; i < 3; i++) {
            cards[i] = {cards[i].second, cards[i].first};
        }
        swap(cov_h, cov_w);
    }
    
    if(cov_h == 2) {
        int w_sum = 0;
        for(int i = 0; i < 3; i++) {
            if(cards[i].first == H) {
                w_sum += cards[i].second;
            }
        }
        if(w_sum >= W) {
            ll ans = 2;
            for(int i = 0; i < 3; i++) {
                if(cards[i].first != H) {
                    ans = (ans * ways(H, W, cards[i].first, cards[i].second)) % MOD;
                }
            }
            cout << ans << endl;
        } else {
            cout << 0 << endl;
        }
        return;
    } else if(cov_h == 3) {
        // TODO
        // cout << "todo" << endl;
        
        int w_sum = 0;
        for(int i = 0; i < 3; i++) {
            w_sum += cards[i].second;
        }
        if(w_sum < W) {
            cout << 0 << endl;
            return;
        }


        ll ans = 0;

        // 2xL 1xR
        for(int r = 0; r < 3; r++) {
            int mx = 0;
            for(int i = 0; i < 3; i++) {
                if(i != r) {
                    mx = max(mx, cards[i].second);
                }
            }
            if(mx + cards[r].second >= W) {
                cerr << "ok " << r << endl;
                ans++;
            }
        }

        ans *= 2;


        // 1xL 1xR
        for(int l = 0; l < 3; l++){
            for(int r = 0; r < 3; r++) {
                if(l == r) continue;
                int m = 3 - l - r;
                // int lo = max(1, W-cards[m].second-1, cards[l].second);
                // int hi = cards[l].second;
                int s = cards[l].second + cards[r].second;
                if(s >= W) {
                        cerr << "1x1x" << ' ' << l << ' ' << r << ' ' << W-cards[m].second-1 << endl;
                    ans += W-cards[m].second-1;
                } else {
                    int hi = min(cards[l].second, W - cards[m].second - 1);
                    int lo = max(1, W - cards[r].second - cards[m].second);

                    int d = (hi - lo + 1);
                    if(d >= 0) {
                        cerr << "1x1x" << ' ' << l << ' ' << r << ' ' << d << endl;
                        ans += d;
                    }
                }
            }
        }

        cout << ans << endl;

        return;
    }

    vector<set<pii>> cand(3);
    for(int i = 0; i < 3; i++) {
        cand[i].insert({0, 0});
        cand[i].insert({H-cards[i].first, 0});
        cand[i].insert({0, W-cards[i].second});
        cand[i].insert({H-cards[i].first, W-cards[i].second});
    }

    int ans = 0;
    for(pii c0 : cand[0]) {
        for(pii c1 : cand[1]) {
            for(pii c2 : cand[2]) {
                vpii pos = {c0, c1, c2};
                if(check(H, W, cards, pos)) {
                    cerr << pos[0].first << ' ' << pos[0].second << ' ' << pos[1].first << ' ' << pos[1].second << ' ' << pos[2].first << ' ' << pos[2].second << endl;
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
    int tc;
    cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3808kb

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

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

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: 0ms
memory: 3852kb

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
3777777774
456790164
0
0
0
0
0
6
2222222222
3555555552
135802502
0
0
0
0
6
2222222222
2222222222
3333333330
814814847
0
0
0
6
2222222222
2222222222
2222222222
3111111108
493827185
0
0
6
2222222222
2222222222
2222222222
2222222222
2888888886
172839523
0
6
2222222222
2222222222
222222222...

result:

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