QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114897#6639. Disk TreejeffqiWA 1ms3568kbC++141.7kb2023-06-23 22:18:522023-06-23 22:18:53

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 22:18:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3568kb
  • [2023-06-23 22:18:52]
  • 提交

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 = -1,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+1,y);
		}
		sort(all(a));
		map<int,Data> c;
		c[-1] = Data();
		vector<array<int,4>> ans;
		for (auto [l,r,k]:a) {
			auto bit = prev(c.upper_bound(l)),eit = c.lower_bound(r);
			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;
		c.erase(c.begin());
		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-1,lst.k});
					assert(lst.k != -1);
				}
				lst = it->se;
			}
		}
		if (n==100) cout << sz(ans) << '\n';
		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: 0ms
memory: 3472kb

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: 1ms
memory: 3508kb

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: 3460kb

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: 0
Accepted
time: 1ms
memory: 3516kb

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 24
18 55 18 24
38 68 38 55
7 82 7 24
35 88 35 55
95 95 95 81
88 95 58 68

result:

ok answer = 1

Test #5:

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

input:

100
490 783 12
666 460 55
561 245 6
223 323 25
3 520 77
225 161 24
514 190 16
997 914 100
412 265 100
374 610 36
296 854 39
601 901 2
307 21 100
390 422 24
940 414 32
332 438 35
553 992 100
235 775 3
656 901 37
770 417 22
649 305 100
448 84 3
375 939 77
910 847 9
776 357 37
743 97 100
371 502 39
508...

output:

101
YES
406 40 406 21
881 52 881 11
891 76 891 11
445 84 445 40
807 97 807 14
842 97 842 52
207 100 207 21
100 115 100 13
432 132 432 40
506 132 506 58
927 132 927 11
968 153 968 132
129 156 129 115
201 161 201 100
420 163 420 40
0 179 0 13
806 183 806 97
498 190 498 132
254 204 254 21
896 204 896 7...

result:

wrong answer Token parameter [name=YES or NO] equals to "101", doesn't correspond to pattern "[A-Za-z]+"