QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#609400 | #9427. Collect the Coins | treasuresgc | WA | 9ms | 5812kb | C++23 | 1.3kb | 2024-10-04 12:46:21 | 2024-10-04 12:46:22 |
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];
bool ach(int x,int y,int v)
{
return abs(t[x]-t[y])*v >= abs(c[x]-c[y]);
}
inline bool check(int v)
{
t[n+1]=2e9;c[n+1]=0;
int num=n;
for(int i=n-1;i>=1;i--)
{
// cout<<ach(i+1,i,v)<<" ";
if(ach(i+1,i,v)) continue;
// cout<<num+1<<" "<<i<<" "<<v<<endl;
// cout<<ach(num+1,i,v)<<endl;
if(ach(num+1,num-1,v))
{
if(ach(num,i,v) || ach(num+1,i,v)) num=i;
else return 0;
continue;
}
if(ach(num+1,i,v)) num=i;
else return 0;
}
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: 0ms
memory: 5612kb
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: 9ms
memory: 5812kb
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 3 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 1 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 1071st lines differ - expected: '165', found: '171'