QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#119116 | #6639. Disk Tree | ideograph_advantage | WA | 1ms | 3468kb | C++17 | 3.1kb | 2023-07-04 23:15:46 | 2023-07-04 23:15:50 |
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(y != b.y) return y < b.y;
return ty > b.ty;
}
};
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);
//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);
}
}
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: 3468kb
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: 3396kb
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: 3452kb
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: -100
Wrong Answer
time: 0ms
memory: 3412kb
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 0 27 29 35 55 35 88 38 0 38 68 58 68 88 95 95 95 95 81
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