QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#281396 | #7785. Three Rectangles | ucup-team197# | WA | 1ms | 3852kb | C++20 | 5.4kb | 2023-12-10 03:43:38 | 2023-12-10 03:43:38 |
Judging History
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'