QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114846#6639. Disk TreejeffqiWA 1ms3552kbC++231.6kb2023-06-23 18:27:592023-06-23 18:28:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-23 18:28:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3552kb
  • [2023-06-23 18:27:59]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
using namespace std;
namespace qiqi {
	struct Data {
		int l,r,k;
		Data(int l = 0,int r = 0,int k = -1):l(max(l,0)),r(r),k(k) {}
		bool friend operator < (Data a,Data b) {
			return a.k < b.k;
		}
	};
	void main() {
		int n; cin >> n;
		vector<Data> a(n);
		for (int i = 0; i < n; i++) {
			int x,y,r;
			cin >> x >> y >> r;
			a[i] = Data(x-r,x+r,y);
		}
		sort(all(a));
		map<int,Data> c; c[0] = Data();
		vector<array<int,4>> ans;
		for (auto [l,r,k]:a) {
			auto bit = prev(c.upper_bound(l)),eit = c.upper_bound(r-1);
			Data col = prev(eit)->se;
			for (auto it = bit; it != eit; it++) {
				int y = it->se.k;
				if (y != -1 && (it == bit || prev(it)->se.r <= it->se.l)) {
					int x = max(l,it->fi);
					ans.pb({x,k,x,y});
				}
			}
			c.erase(next(bit),eit);
			c[l] = Data(l,r,k);
			c.emplace(r,col);
		}
		Data lst;
		for (auto it = c.begin(); it != c.end(); it++) {
			if (it->se.k != -1) {
				if (it != c.begin() && prev(it)->se.r <= it->se.l) {
					ans.pb({it->fi,it->se.k,lst.r,lst.k});
				}
				lst = it->se;
			}
		}
		cout << "YES\n";
		for (auto [a,b,c,d]:ans) {
			cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	qiqi::main();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3552kb

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
0 5 0 0
4 10 4 0

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

2
1 1 1
3 3 1

output:

YES
2 3 2 1

result:

ok answer = 1

Test #3:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

output:

YES
1 10 1 0
19 10 19 0
19 20 19 10
2 20 2 10

result:

ok answer = 1

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3476kb

input:

10
29 29 2
28 55 10
99 81 4
17 82 10
45 88 10
48 68 10
0 8 10
98 95 10
34 0 10
17 24 10

output:

YES
7 24 7 8
24 24 24 0
27 29 27 0
18 55 18 24
27 55 27 29
38 68 38 0
7 82 7 24
35 88 35 55
38 88 38 68
95 95 95 81
88 95 58 68

result:

wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks