QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326378 | #692. Delete the Points | pjshwa | WA | 1ms | 3712kb | C++17 | 1.8kb | 2024-02-12 23:13:04 | 2024-02-12 23:13:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
void fast_io() {
cin.tie(nullptr)->sync_with_stdio(false);
}
void solve() {
int N; cin >> N;
map<int, vector<int>> F;
for (int i = 0; i < N; ++i) {
int x, y; cin >> x >> y;
F[y].push_back(x);
}
vector<tuple<int, int, int, int>> ans;
vector<pair<int, int>> R;
auto sq_len = [&](int x1, int y1, int x2, int y2) {
int maxx = max(x1, x2), minx = min(x1, x2);
int maxy = max(y1, y2), miny = min(y1, y2);
int len = max(maxx - minx, maxy - miny);
return len;
};
auto add_point = [&](int x1, int y1, int x2, int y2) {
int len = sq_len(x1, y1, x2, y2);
int maxx = max(x1, x2), maxy = max(y1, y2);
ans.emplace_back(maxx - len, maxy - len, maxx, maxy);
};
vector<pii> cur;
int px = -1, py = -1;
for (auto& [y, xv] : F) {
for (int x : xv) cur.emplace_back(x, y);
sort(cur.begin(), cur.end());
while (cur.size() >= 2) {
auto [x1, y1] = cur.back(); cur.pop_back();
auto [x2, y2] = cur.back(); cur.pop_back();
if (px != -1 && x2 <= px && px <= x1) {
int plen = sq_len(px, py, x1, y1);
int minx = min(x1, px), maxy = max(y1, py);
ans.emplace_back(minx, maxy - plen, minx + plen, maxy);
px = -1, py = -1;
cur.emplace_back(x2, y2);
}
else add_point(x1, y1, x2, y2);
}
if (cur.empty()) continue;
auto [xr, yr] = cur.back(); cur.pop_back();
if (px == -1) px = xr, py = yr;
else {
add_point(px, py, xr, yr);
px = -1, py = -1;
}
}
cout << "Yes\n";
for (auto [x1, y1, x2, y2] : ans) {
cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
}
}
int main() {
fast_io();
int t = 1;
// cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3544kb
input:
4 1 1 2 2 5 5 6 6
output:
Yes 1 1 2 2 5 5 6 6
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
4 0 0 1 2 2 1 4 4
output:
Yes 0 -1 2 1 1 1 4 4
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 1 2 3 2 2 1 2 3
output:
Yes 2 1 3 2 1 2 2 3
result:
ok OK
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
6 12 9 1 5 10 14 20 14 15 4 7 9
output:
Yes 1 -9 15 5 7 4 12 9 10 4 20 14
result:
ok OK
Test #5:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
10 39 72 59 52 23 17 2 31 30 0 25 88 2 36 61 23 4 96 59 76
output:
Yes 13 0 30 17 2 -28 61 31 2 -5 59 52 39 56 59 76 4 75 25 96
result:
ok OK
Test #6:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
10 53 95 37 51 84 11 3 39 31 20 37 84 42 27 95 38 6 6 16 19
output:
Yes 6 -67 84 11 16 5 31 20 42 -15 95 38 3 17 37 51 37 79 53 95
result:
ok OK
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3712kb
input:
3000 997371332 135791687 997371332 135791686 997371332 135791685 997371333 135791685 997371333 135791687 997371334 135791687 997371333 135791688 997371331 135791686 997371333 135791689 997371334 135791686 997371334 135791689 997371333 135791684 997371332 135791689 997371331 135791685 997371334 13579...
output:
Yes 997371329 135791653 997371330 135791654 997371328 135791653 997371329 135791654 997371324 135791653 997371325 135791654 997371328 135791653 997371330 135791655 997371325 135791653 997371327 135791655 997371331 135791655 997371332 135791656 997371329 135791655 997371330 135791656 997371327 135791...
result:
wrong answer We have 3 point(s) in query 72