QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601506 | #9427. Collect the Coins | ucup-team3474 | WA | 15ms | 7892kb | C++20 | 1.3kb | 2024-09-30 03:02:09 | 2024-09-30 03:02:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
ll w[N],c[N];
bool gao(ll p,ll t,ll w,ll c,ll v){
if(t==-1) return true;
ll dis=w-t;
ll l=p-dis*v,r=p+dis*v;
if(c>=l&&c<=r) return true;
return false;
}
bool check(ll mid){
ll p1=-1,t1=-1;
ll p2=-1,t2=-1;
for(int i=1;i<=n;i++){
if(t1>=t2){
if(gao(p1,t1,w[i],c[i],mid)){
p1=c[i];
t1=w[i];
}else if(gao(p2,t2,w[i],c[i],mid)){
p2=c[i];
t2=w[i];
}else return false;
}else{
if(gao(p2,t2,w[i],c[i],mid)){
p2=c[i];
t2=w[i];
}else if(gao(p1,t1,w[i],c[i],mid)){
p1=c[i];
t1=w[i];
}
else return false;
}
}
return true;
}
void __(){
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld%lld",&w[i],&c[i]);
ll l=0,r=2e9;
if(!check(r)){
puts("-1");
return;
}
while(l<r){
ll mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%lld\n",l);
}
int main(){
int _=1;
cin>>_;
while(_--){
__();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5940kb
input:
3 5 1 1 3 7 3 4 4 3 5 10 1 10 100 3 10 100 10 1000 10 10000
output:
2 0 -1
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 15ms
memory: 7892kb
input:
1135 2 6 5 8 8 8 2 9 2 10 4 4 5 3 6 2 6 8 8 2 8 7 1 9 1 6 4 6 6 1 6 2 9 10 10 1 10 7 5 1 6 2 5 6 7 8 6 10 3 8 1 10 5 4 5 7 6 1 6 6 8 4 9 1 9 4 8 1 1 1 3 2 9 3 3 5 9 6 10 9 7 10 7 3 5 8 6 6 10 6 7 2 9 4 7 5 10 6 3 6 7 8 9 10 1 6 1 4 2 8 5 9 7 10 9 1 10 5 9 2 7 4 5 5 9 6 10 7 4 9 4 9 9 10 3 10 7 1 3 1...
output:
0 3 0 3 1 3 6 0 3 2 2 0 2 5 0 1 5 1 2 0 0 0 1 4 2 0 2 1 3 0 3 2 3 2 5 4 1 1 0 1 1 1 0 2 0 1 0 1 0 2 1 0 2 3 4 4 1 1 1 0 1 3 0 1 4 4 3 0 0 2 2 6 4 2 1 0 0 1 0 2 1 2 0 1 5 3 0 0 1 2 0 3 0 2 2 2 1 0 0 0 5 1 2 0 6 1 1 1 2 2 2 0 3 1 4 3 6 0 8 1 1 3 0 2 2 4 1 1 0 0 0 7 2 2 1 0 0 3 1 2 1 1 2 5 3 0 3 3 3 5 ...
result:
wrong answer 36th lines differ - expected: '3', found: '4'