QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#281386 | #7785. Three Rectangles | ucup-team197# | WA | 7ms | 3492kb | C++20 | 4.8kb | 2023-12-10 03:34:27 | 2023-12-10 03:34:27 |
Judging History
answer
#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(cards[i].first, 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) {
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)) {
ans++;
}
}
}
}
cout << ans << endl;
}
int main() {
int tc;
cin >> tc;
while(tc--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3464kb
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: 3468kb
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: 3408kb
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: 7ms
memory: 3492kb
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'