QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#119118 | #6639. Disk Tree | ideograph_advantage | WA | 1ms | 3508kb | C++17 | 3.3kb | 2023-07-04 23:31:32 | 2023-07-04 23:31:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cerr << *l << " ", l++;
cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
typedef long long ll;
//typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
struct event{
int x, y, ty;
bool operator<(event b){
if(x != b.x) return x < b.x;
if(ty != b.ty) return ty > b.ty;
return y < b.y;
}
};
int main(){
StarBurstStream;
int n;
cin >> n;
vector<event> ev;
for(int i = 0; i < n; i++){
int x, y, r;
cin >> x >> y >> r;
ev.pb(event({x - r, y, 1}));
ev.pb(event({x + r, y, -1}));
}
sort(iter(ev));
set<int> st;
pii lst = mp(-1, -1);
vector<pair<pii, pii>> ans;
for(int i = 0; i < 2 * n; ){
int x = ev[i].x;
vector<int> tmp;
for(; i < 2 * n && ev[i].x == x && ev[i].ty == 1; i++){
tmp.pb(ev[i].y);
st.insert(ev[i].y);
}
//debug("test", x);
//if(i < 2 * n) debug("OAO", ev[i].x, ev[i].y, ev[i].ty);
//pary(iter(tmp));
//pary(iter(st));
bool up = false;
for(int j = 0; j < SZ(tmp); j++){
int y = tmp[j];
auto it = st.find(y);
if(it != st.begin() && (j && *prev(it) != tmp[j - 1])) up = false;
if(!up && it != st.begin()){
ans.pb(mp(mp(x, *prev(it)), mp(x, y)));
//debug("pb", y, mp(x, *prev(it)));
}
else if(next(it) != st.end()){
ans.pb(mp(mp(x, *next(it)), mp(x, y)));
up = true;
//debug("pb", y, mp(x, *next(it)));
}
else if(lst != mp(-1, -1)){
ans.pb(mp(lst, mp(x, y)));
//debug("pb", lst);
}
}
for(; i < 2 * n && ev[i].x == x && ev[i].ty == -1; i++){
st.erase(ev[i].y);
lst = mp(x, ev[i].y);
}
//debug("ok", x);
//if(i < 2 * n) debug("OAO", ev[i].x, ev[i].y, ev[i].ty);
}
cout << "YES\n";
for(auto [a, b] : ans){
a.ff = max(a.ff, 0);
b.ff = max(b.ff, 0);
cout << a.ff << " " << a.ss << " " << b.ff << " " << b.ss << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3448kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 0 0 5 4 0 4 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
2 1 1 1 3 3 1
output:
YES 2 1 2 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 10 1 0 2 10 2 20 19 10 19 0 19 10 19 20
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3396kb
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 8 7 24 7 24 7 82 18 24 18 55 24 24 24 0 27 24 27 29 35 55 35 88 38 55 38 68 58 68 88 95 95 95 95 81
result:
ok answer = 1
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3480kb
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:
YES 0 520 0 179 0 179 0 13 0 520 0 773 0 179 0 366 0 520 0 663 7 773 7 952 20 520 20 607 39 773 39 843 60 663 60 703 63 843 63 850 64 179 64 226 75 773 75 790 81 13 81 208 100 13 100 115 111 366 111 603 120 366 120 512 129 115 129 156 134 156 134 241 176 241 176 100 179 703 179 934 198 241 198 323 2...
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