| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 787394 |
2023-07-19T06:46:40 Z |
이동현(#10034) |
Hamburg Steak (JOI20_hamburg) |
C++17 |
|
3000 ms |
1384 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<vector<int>> a(n, vector<int>(4));
for(int i = 0; i < n; ++i){
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
}
auto solve4 = [&](vector<vector<int>> a, int onex, int oney)->void{
int n = (int)a.size();
if(!n){
for(int i = 0; i < 4; ++i){
cout << onex << ' ' << oney << '\n';
}
exit(0);
}
auto chk = [&](vector<vector<int>> x, vector<vector<int>> pos){
for(int i = 0; i < (int)x.size(); ++i){
int ok = 0;
for(auto&j:pos){
if(j[0] >= x[i][0] && j[0] <= x[i][2] && j[1] >= x[i][1] && j[1] <= x[i][3]){
ok = 1;
break;
}
}
if(!ok) return 0;
}
return 1;
};
auto solve1 = [&](vector<vector<int>> x)->vector<int>{
int xp = 1, yp = 1;
for(int i = 0; i < (int)x.size(); ++i){
xp = max(xp, x[i][0]);
yp = max(yp, x[i][1]);
}
if(chk(x, {{xp, yp}})){
return {1, xp, yp};
}
return {0};
};
int xu = (int)2e9, xd = -1, yl = (int)2e9, yr = -1;
for(int i = 0; i < n; ++i){
xu = min(xu, a[i][2]);
xd = max(xd, a[i][0]);
yl = min(yl, a[i][3]);
yr = max(yr, a[i][1]);
}
auto solveline = [&](vector<vector<int>> x){
vector<int> rv;
sort(x.begin(), x.end(), [&](vector<int>&a, vector<int>&b){return a[1] < b[1];});
for(int i = 0; i < (int)x.size(); ++i){
if(!(int)rv.size() || rv.back() < x[i][0]){
rv.push_back(x[i][1]);
}
}
return rv;
};
if(xd <= xu){
vector<vector<int>> x(n);
for(int i = 0; i < n; ++i){
x[i] = {a[i][1], a[i][3]};
}
auto rv = solveline(x);
if((int)rv.size() <= 3){
for(int i = 0; i < 3; ++i){
cout << xd << ' ' << (i < (int)rv.size() ? rv[i] : rv.back()) << '\n';
}
cout << onex << ' ' << oney << '\n';
exit(0);
}
return;
}
if(yr <= yl){
vector<vector<int>> x(n);
for(int i = 0; i < n; ++i){
x[i] = {a[i][0], a[i][2]};
}
auto rv = solveline(x);
if((int)rv.size() <= 3){
for(int i = 0; i < 3; ++i){
cout << (i < (int)rv.size() ? rv[i] : rv.back()) << ' ' << yl << '\n';
}
cout << onex << ' ' << oney << '\n';
exit(0);
}
return;
}
auto solve2 = [&](vector<vector<int>> x, int px, int py, int ppx, int ppy){
vector<vector<int>> nxt;
for(auto&i:x){
if(!(px >= i[0] && px <= i[2] && py >= i[1] && py <= i[3])){
nxt.push_back(i);
}
}
auto rv = solve1(nxt);
if(rv[0] == 1){
cout << px << ' ' << py << '\n' << rv[1] << ' ' << rv[2] << '\n' << ppx << ' ' << ppy << '\n';
cout << onex << ' ' << oney << '\n';
exit(0);
}
};
auto solve3 = [&](vector<vector<int>> x, int px, int py){
vector<vector<int>> nxt;
for(auto&i:x){
if(!(px >= i[0] && px <= i[2] && py >= i[1] && py <= i[3])){
nxt.push_back(i);
}
}
int xu = (int)2e9, yl = (int)2e9, yr = -1;
for(int i = 0; i < (int)nxt.size(); ++i){
xu = min(xu, nxt[i][2]);
yl = min(yl, nxt[i][3]);
yr = max(yr, nxt[i][1]);
}
solve2(nxt, xu, yl, px, py);
solve2(nxt, xu, yr, px, py);
};
solve3(a, xu, yl);
solve3(a, xu, yr);
solve3(a, xd, yl);
solve3(a, xd, yr);
};
int x1 = (int)2e9;
for(int i = 0; i < n; ++i){
x1 = min(x1, a[i][2]);
}
for(int i = n - 1; i >= 0; --i){
vector<vector<int>> nxt;
auto sol = [&](int px, int py){
vector<vector<int>> nxt;
for(auto&i:a){
if(!(px >= i[0] && px <= i[2] && py >= i[1] && py <= i[3])){
nxt.push_back(i);
}
}
solve4(nxt, px, py);
};
sol(x1, a[i][1]);
sol(x1, a[i][3]);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
856 KB |
Output is correct |
| 2 |
Correct |
6 ms |
724 KB |
Output is correct |
| 3 |
Correct |
87 ms |
808 KB |
Output is correct |
| 4 |
Correct |
5 ms |
724 KB |
Output is correct |
| 5 |
Correct |
107 ms |
872 KB |
Output is correct |
| 6 |
Correct |
7 ms |
852 KB |
Output is correct |
| 7 |
Execution timed out |
3032 ms |
1384 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
856 KB |
Output is correct |
| 2 |
Correct |
6 ms |
724 KB |
Output is correct |
| 3 |
Correct |
87 ms |
808 KB |
Output is correct |
| 4 |
Correct |
5 ms |
724 KB |
Output is correct |
| 5 |
Correct |
107 ms |
872 KB |
Output is correct |
| 6 |
Correct |
7 ms |
852 KB |
Output is correct |
| 7 |
Execution timed out |
3032 ms |
1384 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
