QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326373 | #692. Delete the Points | pjshwa | WA | 1ms | 3824kb | C++17 | 1.9kb | 2024-02-12 23:09:45 | 2024-02-12 23:09:46 |
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, x2), maxx = max(x1, x2);
int miny = min(y1, y2), maxy = max(y1, y2);
ans.emplace_back(minx, miny, minx + plen, miny + plen);
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: 3536kb
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: 3824kb
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: -100
Wrong Answer
time: 0ms
memory: 3580kb
input:
4 1 2 3 2 2 1 2 3
output:
Yes 1 2 2 3 1 2 2 3
result:
wrong answer We have 0 point(s) in query 1