QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #564040 | #3224. Directions | dongyc666 | WA | 95ms | 13196kb | C++14 | 2.5kb | 2024-09-14 19:15:20 | 2024-09-14 19:15:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NR=2e5+10;
int n,x[NR],y[NR],w[NR],len,pre[NR],suf[NR],ans=1e18;
struct task{
int x,y,val,opt;
bool operator <(const task &T)const{
return y*T.x<T.y*x;
}
}t[NR];
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
map<pii,int>mp;
vector<int>buc;
#define pb emplace_back
void solve(){
sort(t+1,t+1+len);
memset(pre,999999,sizeof(pre));
memset(suf,999999,sizeof(suf));
// for(int i=1;i<=len;i++)printf("%lld %lld %lld %lld\n",t[i].x,t[i].y,t[i].val,t[i].opt);
for(int i=1;i<=len;i++)
if(t[i].opt==0)pre[i]=min(pre[i-1],t[i].val);
else pre[i]=pre[i-1];
for(int i=len;i>=1;i--)
if(t[i].opt==0)suf[i]=min(suf[i+1],t[i].val);
else suf[i]=suf[i+1];
for(int i=1;i<=len;i++)
if(t[i].opt==1){
int p1=i-1,p2=i+1;
if(t[p1].x==t[i].x&&t[p1].y==t[i].y)p1--;
if(t[p2].x==t[i].x&&t[p2].y==t[i].y)p2++;
// printf("i:%lld %lld %lld\n",i,p1,p2);
ans=min(ans,pre[p1]+suf[p2]+t[i].val);
}
// cout<<ans<<endl;
// puts("-----");
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>w[i];
if(!x[i]&&!y[i])continue;
int d=__gcd(x[i],y[i]);
x[i]/=d;y[i]/=d;
if(mp[mkp(x[i],y[i])])mp[mkp(x[i],y[i])]=min(mp[mkp(x[i],y[i])],w[i]);
else mp[mkp(x[i],y[i])]=w[i];
}
len=0;
for(auto lcy:mp){
int x=lcy.fi.fi,y=lcy.fi.se,val=lcy.se;
if(!x){
if(y>0)y=2e9,x=1;
else y=-2e9,x=-1;
}
if(x<0)t[++len]=task{-x,y,val,1};
else t[++len]=task{x,y,val,0};
}
solve();
len=0;
for(auto lcy:mp){
int x=lcy.fi.fi,y=lcy.fi.se,val=lcy.se;
if(!x){
if(y>0)y=2e9,x=-1;
else y=-2e9,x=1;
}
if(x>0)t[++len]=task{x,y,val,1};
else t[++len]=task{-x,y,val,0};
}
solve();
// len=0;
// for(auto lcy:mp){
// int x=lcy.fi.se,y=lcy.fi.fi,val=lcy.se;
// if(!x){
// if(y>0)y=2e9,x=1;
// else y=-2e9,x=-1;
// }
// if(x<0)t[++len]=task{-x,y,val,1};
// else t[++len]=task{x,y,val,0};
// }
// solve();
// len=0;
// for(auto lcy:mp){
// int x=lcy.fi.se,y=lcy.fi.fi,val=lcy.se;
// if(!x){
// if(y>0)y=2e9,x=-1;
// else y=-2e9,x=1;
// }
// if(x>0)t[++len]=task{x,y,val,1};
// else t[++len]=task{-x,y,val,0};
// }
// solve();
for(auto lcy:mp){
int x=lcy.fi.se,y=lcy.fi.fi,val=lcy.se;
if(mp.count(mkp(-x,-y)))buc.pb(val+mp[mkp(-x,-y)]);
}
sort(buc.begin(),buc.end());
if(buc.size()>2)ans=min(ans,buc[0]+buc[2]);
if(ans<1e18)cout<<ans<<endl;
else puts("-1");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 58ms
memory: 11620kb
input:
200000 -1 -1 1 1 1 1 0 1 1 1 0 1 1 -1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 0 1 1 0 0 1 0 0 1 1 -1 1 -1 -1 1 0 0 1 1 0 1 -1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 0 -1 1 1 -1 1 -1 0 1 1 0 1 1 -1 1 0 -1 1 1 0 1 -1 1 1 1 0 1 -1 0 1 1 1 1 1 0 1 -1 -1 1 -1 1 1 -1 -1 1 0 -1 1 0 -1 1 1 1 1 1 -1 1 0 1 1 1 1 1 -1 1 1 1 -1 1 0...
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 59ms
memory: 13196kb
input:
200000 -1 -1 2 1 0 1 1 0 2 1 -1 2 1 0 1 -1 1 1 -1 -1 2 1 1 1 0 -1 2 -1 -1 1 0 1 2 0 -1 2 -1 0 2 0 0 2 -1 1 1 1 1 1 -1 0 1 1 -1 2 1 0 1 0 0 1 1 0 2 0 -1 1 0 1 1 0 -1 2 -1 1 2 0 1 2 -1 1 2 0 1 1 0 1 1 1 1 2 1 1 1 1 0 2 1 1 2 -1 1 2 -1 1 1 0 1 2 0 -1 2 1 0 2 0 1 1 0 -1 1 1 -1 1 1 0 2 0 -1 1 -1 0 1 0 -1...
output:
3
result:
ok single line: '3'
Test #3:
score: -100
Wrong Answer
time: 95ms
memory: 13152kb
input:
200000 1 0 555860533 -1 1 633479355 0 0 411890838 -1 -1 411764668 0 0 324117889 1 1 147426106 1 0 41681213 1 -1 169580394 1 -1 204074237 -1 1 265787176 1 -1 204010614 0 -1 582574240 0 -1 98238758 1 1 489573021 -1 1 747647275 1 -1 933893240 0 -1 663924164 0 0 470849190 1 -1 479419247 -1 -1 53695974 0...
output:
98276
result:
wrong answer 1st lines differ - expected: '95355', found: '98276'