QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#239090 | #6563. Four Square | Fyind# | AC ✓ | 1ms | 3828kb | C++17 | 2.4kb | 2023-11-04 18:26:45 | 2023-11-04 18:26:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
int n, m;
bool solve(int x,int y, vector<pii> A) {
if (x <= 0 || y <= 0) return false;
if (sz(A) == 1) {
pii s = A[0];
return s.first == x && s.second == y || s.second == x && s.first == y;
}
for (int k = 0;k < sz(A); ++k) if (A[k].first <= x && A[k].second <= y) {
vector<pii> rest;
for (int i = 0;i < sz(A); ++i) if (i != k) rest.push_back(A[i]);
auto distri = [&](pii na,pii nb) {
if (nb.first == 0 || nb.second == 0) {
return solve(na.first,na.second,rest);
}
if (na.first == 0 || na.second == 0) {
return solve(nb.first,nb.second,rest);
}
for (int t = 0;t < sz(rest); ++t) {
vector<pii> ra, rb;
ra.push_back(rest[t]);
for (int j = 0;j < sz(rest); ++j) if (j != t) {
rb.push_back(rest[j]);
}
if (solve(na.first,na.second,ra) && solve(nb.first,nb.second,rb)) return true;
}
return false;
};
pii na = {x-A[k].second, A[k].first}, nb = {y-A[k].first,x};
if (distri(na,nb)) return true;
na = {x-A[k].second,y}; nb = {A[k].second,y-A[k].first};
if (distri(na,nb)) return true;
na = {x-A[k].first,A[k].second}; nb = {y-A[k].second,x};
if (distri(na,nb)) return true;
na = {x-A[k].first,y}; nb = {y-A[k].second,A[k].first};
if (distri(na,nb)) return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<pii> sq;
vector<int> val;
for (int i = 1;i <= 4; ++i) {
int x,y; cin >> x >> y;
sq.push_back({x,y});
val.push_back(x); val.push_back(y);
}
int len = sz(val);
for (int i = 0;i < len; ++i) {
for (int j = i+1;j < len; ++j) {
val.push_back(val[i]+val[j]);
}
}
sort(val.begin(),val.end());
val.erase(unique(val.begin(),val.end()),val.end());
for (auto x : val) {
if (solve(x,x,sq)) {
cout << "1" << '\n';
return 0;
}
}
cout << '0' << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
1 1 1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 1 3 3 2 2 3 3
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 8 2 8 2 8 2 8
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 3 5 5 3 3 3 5
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 2 4 8 16 32 64 128
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
4 4 2 1 4 4 2 1
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
995 51 559 565 154 536 56 780
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
391 694 540 42 240 937 691 246
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
519 411 782 710 299 45 21 397
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
96 960 948 18 108 82 371 576
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
3 2 4 3 3 1 1 4
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
4 3 1 2 4 4 3 2
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
4 4 1 3 5 4 2 5
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1000 1000 1000 1000 1000 1000 1000 1000
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1000 999 998 1000 997 1000 997 997
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
1 3 3 3 3 3 4 7
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 5 5 4 7 1 6 2
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
12 2 12 7 7 12 16 4
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
7 2 2 14 5 14 7 12
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
32 36 5 1 1 37 35 5
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
28 30 30 1 31 1 2 30
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
66 68 9 11 7 66 9 64
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
59 44 25 44 40 32 40 52
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 4 2 3 4 2 3 2
output:
1
result:
ok single line: '1'