QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#609365 | #9427. Collect the Coins | treasuresgc | WA | 4ms | 5820kb | C++23 | 1.2kb | 2024-10-04 12:29:58 | 2024-10-04 12:30:02 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int sum=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}
while(isdigit(ch)){sum=sum*10+ch-48;ch=getchar();}
return sum*f;
}
int n;
int t[1000005];
int c[1000005];
inline bool check(int v)
{
int pos=0,tim=2e9;
for(int i=n-1;i>=1;i--)
{
// cout<<v<<" "<<pos<<" "<<tim<<endl;
// cout<<abs(t[i]-t[i+1])*v<<" "<<abs(c[i]-c[i+1])<<endl;
// cout<<abs(c[i]-pos)<<" "<<abs(tim-t[i])*v<<endl;
if(abs(t[i]-t[i+1])*v >= abs(c[i]-c[i+1])) continue;
if(abs(c[i]-pos) > abs(tim-t[i])*v) return 0;
pos=c[i+1],tim=t[i+1];
}
return 1;
}
inline bool sub()
{
int c1=-1,c2=-1;
for(int i=1;i<=n;i++)
{
if(c1==c[i] || c2==c[i]) continue;
if(c1==-1) c1=c[i];
else if(c2==-1) c2=c[i];
else return 0;
}
cout<<0<<endl;
return 1;
}
inline void solve()
{
n=read();
for(int i=1;i<=n;i++) t[i]=read(),c[i]=read();
if(sub()) return;
int L=1,R=1000000000,ans=-1;
while(L<=R)
{
int mid=(L+R)>>1;
if(check(mid)) R=mid-1,ans=mid;
else L=mid+1;
}
cout<<ans<<endl;
}
signed main()
{
int T;
T=read();
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5732kb
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: 4ms
memory: 5820kb
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 6 1 2 0 0 0 1 4 4 0 2 1 3 0 3 2 3 2 5 4 1 1 0 1 1 1 0 3 0 1 0 1 0 2 1 0 2 3 4 7 1 1 1 0 1 3 0 1 4 4 4 0 0 2 2 6 4 3 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 8 3 0 3 3 3 5 ...
result:
wrong answer 17th lines differ - expected: '5', found: '6'