QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123560 | #6639. Disk Tree | installb | WA | 2ms | 11672kb | C++14 | 2.7kb | 2023-07-12 21:06:53 | 2023-07-12 21:06:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400005;
struct interval{
int l,r,pos,id;
bool operator < (const interval &o)const{
if(l == o.l) return pos < o.pos;
return l < o.l;
}
}s[N];
set <pair <int,int> > st;
vector <tuple <int,int,int,int> > ans;
int n,x[N],y[N],r[N];
pair <int,int> lis[N << 2]; int lsc = 0;
void solve(){
cin >> n;
for(int i = 1;i <= n;i ++){
cin >> x[i] >> y[i] >> r[i];
s[i] = {x[i] - r[i],x[i] + r[i],y[i],i};
}
sort(s + 1,s + 1 + n);
// x has to be >= 0, so connect all possible circles with x = 0 first
int pos = 0;
for(int i = 1;i <= n;i ++){
if(x[s[i].id] - r[s[i].id] <= 0) pos = i;
else break;
}
vector <pair <int,int> > G;
for(int i = 1;i <= pos;i ++){
G.push_back({y[s[i].id],s[i].id});
st.insert({y[s[i].id],s[i].id});
}
sort(G.begin(),G.end());
for(int i = 1;i < G.size();i ++){
int u = G[i - 1].second,v = G[i].second;
ans.push_back({0,y[u],0,y[v]});
}
pair <int,int> mxr = {-1,-1};
for(int i = 1;i <= pos;i ++) mxr = max(mxr,{x[s[i].id] + r[s[i].id],s[i].id});
for(int i = pos + 1;i <= n;i ++){
int u = s[i].id,id = -1;
while(st.size()){
auto it = st.lower_bound({y[u],-1});
if(it == st.end()) break;
int v = it->second;
if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
else{
id = v;
break;
}
}
if(id == -1){
while(st.size()){
auto it = -- st.lower_bound({y[u],-1});
int v = it->second;
if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
else{
id = v;
break;
}
}
}
if(id == -1 && i > 1) ans.push_back({mxr.first,y[mxr.second],x[u] - r[u],y[u]});
else{
lis[++ lsc] = {x[u] - r[u],y[id]};
lis[++ lsc] = {x[u] - r[u],y[u]};
// ans.push_back({x[u] - r[u],y[id],x[u] - r[u],y[u]});
}
st.insert({y[u],u});
mxr = max(mxr,{x[u] + r[u],u});
}
sort(lis + 1,lis + 1 + lsc);
lsc = unique(lis + 1,lis + 1 + lsc) - lis - 1;
for(int i = 2;i <= lsc;i ++){
if(lis[i].first == lis[i - 1].first) ans.push_back({lis[i - 1].first,lis[i - 1].second,lis[i].first,lis[i].second});
}
if(ans.size() != n - 1) cout << ans.size() << endl;
cout << "YES\n";
for(auto [a,b,c,d] : ans) cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9656kb
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: 2ms
memory: 11600kb
input:
2 1 1 1 3 3 1
output:
YES 2 1 2 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 2ms
memory: 11672kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 0 1 10 2 10 2 20 19 0 19 10 19 10 19 20
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 2ms
memory: 9548kb
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 58 68 88 95 7 8 7 24 7 24 7 82 18 55 18 82 24 0 24 24 27 29 27 55 35 55 35 88 38 68 38 88 95 81 95 95
result:
ok answer = 1
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 11616kb
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:
102 YES 0 13 0 179 0 179 0 366 0 366 0 520 0 520 0 663 0 663 0 773 7 773 7 952 20 607 20 663 39 843 39 952 60 703 60 773 63 850 63 952 64 226 64 366 75 790 75 850 81 208 81 226 100 115 100 208 111 603 111 703 120 512 120 603 129 156 129 366 134 241 134 366 176 100 176 241 179 703 179 934 198 323 198...
result:
wrong answer Token parameter [name=YES or NO] equals to "102", doesn't correspond to pattern "[A-Za-z]+"