QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#433144#6639. Disk Treeucup-team3215WA 1ms3840kbC++201.1kb2024-06-08 05:28:272024-06-08 05:28:28

Judging History

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

  • [2024-06-08 05:28:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2024-06-08 05:28:27]
  • 提交

answer

#include <algorithm>
#include <array>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n; cin >> n;
  vector<array<int, 2>> ev;
  for (int i = 0; i < n; ++i) {
    int x, y, r; cin >> x >> y >> r;
    ev.push_back({max(y - r, 0), ~x});
    ev.push_back({y + r, x});
  }
  sort(ev.begin(), ev.end());
  array<int, 2> dead{-1};
  multiset<int> live;
  cout << "YES\n";
  for (int i = 0; i < 2 * n; ++i) {
    auto [y, x] = ev[i];
    if (x >= 0) live.erase(live.find(x)), dead = {x, y};
    else if (auto it = live.insert(x = ~x); next(it) != live.end()) cout << x << ' ' << y << ' ' << *next(it) << ' ' << y << '\n';
    else if (it != live.begin()) {
      int j = i;
      while (i + 1 != 2 * n && ev[i + 1][0] == y && ~ev[i + 1][1] > *prev(it)) ++i;
      for (int k = i; k >= j; --k) cout << ~ev[k][1] << ' ' << y << ' ' << *prev(it) << ' ' << y << '\n', live.insert(~ev[k][1]);
    } else if (~dead[0]) cout << x << ' ' << y << ' ' << dead[0] << ' ' << dead[1] << '\n';
  }
}

详细

Test #1:

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

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
10 4 1 3
0 4 10 4

result:

ok answer = 1

Test #2:

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

input:

2
1 1 1
3 3 1

output:

YES
3 2 1 2

result:

ok answer = 1

Test #3:

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

input:

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

output:

YES
10 0 20 0
2 0 10 0
20 19 10 19
3 19 10 19

result:

ok answer = 1

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3840kb

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
0 0 34 0
17 14 0 14
29 27 17 27
28 45 29 45
48 58 29 58
17 72 29 72
99 77 48 77
45 78 48 78
98 85 99 85

result:

wrong answer Two disks cannot reach eachother