QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#175440 | #6563. Four Square | Nadim | AC ✓ | 1ms | 3852kb | C++20 | 4.7kb | 2023-09-10 18:11:03 | 2023-09-10 18:11:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"["<<#x<<": "<<x<<"]\n"
#define debug2(x, y) cout<<"["<<#x<<": "<<x<<"]"<<" ["<<#y<<": "<<y<<"]\n"
#define debug3(x, y, z) cout<<"["<<#x<<": "<<x<<"]"<<" ["<<#y<<": "<<y<<"]"<<" ["<<#z<<": "<<z<<"]\n"
#define debug4(x, y, z, k) cout<<"["<<#x<<": "<<x<<"]"<<" ["<<#y<<": "<<y<<"]"<<" ["<<#z<<": "<<z<<"]"<<" ["<<#k<<": "<<k<<"]\n"
#define debug5(x, y, z, k, m) cout<<"["<<#x<<": "<<x<<"]"<<" ["<<#y<<": "<<y<<"]"<<" ["<<#z<<": "<<z<<"]"<<" ["<<#k<<": "<<k<<"]"<<" ["<<#m<<": "<<m<<"]\n"
#define debug6(x, y, z, k, m, n) cout<<"["<<#x<<": "<<x<<"]"<<" ["<<#y<<": "<<y<<"]"<<" ["<<#z<<": "<<z<<"]"<<" ["<<#k<<": "<<k<<"]"<<" ["<<#m<<": "<<m<<"]"<<" ["<<#n<<": "<<n<<"]\n"
const int n = 4;
int poss1(vector<pair<int,int>> now, int w, int h) {
assert(now.size() == 1);
if(w <= 0 || h <= 0) return 0;
if(now[0].first == w && now[0].second == h) return 1;
if(now[0].second == w && now[0].first == h) return 1;
return 0;
}
int poss2(vector<pair<int,int>> now, int w, int h) {
assert(now.size() == 2);
if(w <= 0 || h <= 0) return 0;
for(int i=0; i<2; i++) {
vector<pair<int,int>> pass;
for(int j=0; j<2; j++) if(j != i) {
pass.push_back(now[j]);
}
if(now[i].first == w) return poss1(pass, w, h - now[i].second);
if(now[i].second == w) return poss1(pass, w, h - now[i].first);
if(now[i].first == h) return poss1(pass, w-now[i].second, h);
if(now[i].second == h) return poss1(pass, w-now[i].first, h);
}
return 0;
}
int poss3(vector<pair<int,int>> now, int w, int h) {
assert(now.size() == 3);
//debug2(w, h);
if(w <= 0 || h <= 0) return 0;
for(int i=0; i<3; i++) {
vector<pair<int,int>> pass;
for(int j=0; j<3; j++) if(j != i) {
pass.push_back(now[j]);
}
if(now[i].first == w) return poss2(pass, w, h - now[i].second);
if(now[i].second == w) return poss2(pass, w, h - now[i].first);
if(now[i].first == h) return poss2(pass, w-now[i].second, h);
if(now[i].second == h) return poss2(pass, w-now[i].first, h);
}
return 0;
}
int poss4(vector<pair<int,int>> a, int len) {
assert(a.size() == 4);
for(int i=0; i<n; i++) {
vector<pair<int,int>> pass;
for(int j=0; j<n; j++) if(j != i) {
pass.push_back(a[j]);
}
if(a[i].first == len) return poss3(pass, len, len - a[i].second);
if(a[i].second == len) return poss3(pass, len, len - a[i].first);
}
//debug(33);
int ok = 0;
//check the cases where above 2 block form a rectangle
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) if(j != i) {
vector<pair<int,int>> pass;
for(int k=0; k<n; k++) {
if(k == i || k==j) continue;
pass.push_back(a[k]);
}
for(int mask=0; mask<4; mask++) {
vector<pair<int,int>> now = {a[i], a[j]};
for(int at = 0; at < 2; at++) {
if((mask&(1<<at))) swap(now[at].first, now[at].second);
}
if(now[0].first + now[1].first == len && now[0].second == now[1].second) ok |= poss2(pass, len, len - now[0].second);
}
}
}
//above 2 doesnt form a rectangle
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) if(j != i) {
for(int k=0; k<n; k++) if(k != i && k != j) {
for(int l=0; l<n; l++) if(l != i && l !=j && l != k) {
for(int mask=0; mask < 16; mask++) {
vector<pair<int,int>> now = {a[i], a[j], a[k], a[l]};
for(int at = 0; at < n; at++) if((mask&(1<<at))) {
swap(now[at].first, now[at].second);
}
if(now[0].first + now[1].first == len
&& now[0].first == now[2].first
&& now[1].first == now[3].first
&& now[0].second + now[2].second == len
&& now[1].second + now[3].second == len) return 1;
}
}
}
}
}
return ok;
}
int main() {
vector<pair<int,int>> a(n);
int area = 0;
for(int i=0; i<n; i++) {
cin>> a[i].first >> a[i].second;
area += a[i].first * a[i].second;
}
int len = sqrt(area);
while(len * len < area) len++;
if(len*len > area) {
cout<< 0 << endl;
return 0;
}
//debug(len);
if(poss4(a, len)) cout<< 1 << endl;
else cout<< 0 << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3552kb
input:
1 1 1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
3 1 3 3 2 2 3 3
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
2 8 2 8 2 8 2 8
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
5 3 5 5 3 3 3 5
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
1 2 4 8 16 32 64 128
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
4 4 2 1 4 4 2 1
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
995 51 559 565 154 536 56 780
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
391 694 540 42 240 937 691 246
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
519 411 782 710 299 45 21 397
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
96 960 948 18 108 82 371 576
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
3 2 4 3 3 1 1 4
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
4 3 1 2 4 4 3 2
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
4 4 1 3 5 4 2 5
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
1000 1000 1000 1000 1000 1000 1000 1000
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
1000 999 998 1000 997 1000 997 997
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
1 3 3 3 3 3 4 7
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 5 5 4 7 1 6 2
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
12 2 12 7 7 12 16 4
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
7 2 2 14 5 14 7 12
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
32 36 5 1 1 37 35 5
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
28 30 30 1 31 1 2 30
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
66 68 9 11 7 66 9 64
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
59 44 25 44 40 32 40 52
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
4 4 2 3 4 2 3 2
output:
1
result:
ok single line: '1'