QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#612601 | #9427. Collect the Coins | zhouhuanyi | WA | 22ms | 7984kb | C++23 | 1.6kb | 2024-10-05 12:14:22 | 2024-10-05 12:14:23 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1000000
using namespace std;
const long long inf=(long long)(1e18);
const int INF=(int)(1e9);
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int t,c;
};
reads st[N+1],delta[N+1];
struct rds
{
long long a,b;
int num;
bool operator < (const rds &t)const
{
return a!=t.a?a<t.a:b<t.b;
}
};
rds tong[N+1];
bool used[N+1];
int T,n,length;
bool check(int x)
{
int l=1;
long long minn;
for (int i=1;i<=n;++i) used[i]=0;
for (int i=1;i<=n-1;++i)
if (abs(st[i+1].c-st[i].c)>1ll*(st[i+1].t-st[i].t)*x)
{
if (l==1)
{
for (int j=2;j<=i+1;++j) used[j]=1;
}
else
{
length=0;
for (int j=max(l-1,1);j<=i+1;++j) tong[++length]=(rds){1ll*st[j].t*x-st[j].c,1ll*st[j].t*x+st[j].c,j};
sort(tong+1,tong+length+1),minn=inf<<1;
for (int j=1;j<=length;++j)
{
if (minn<=tong[j].b) used[tong[j].num]=1;
if (used[tong[j].num+1]) minn=min(minn,tong[j].b);
}
}
l=i+1;
}
if (l==1) return 1;
for (int i=n;i>=1;--i)
{
if (i!=n&&abs(st[i+1].c-st[i].c)>1ll*(st[i+1].t-st[i].t)*x) return 0;
if (used[i]) return 1;
}
}
int main()
{
int res;
T=read();
while (T--)
{
n=read(),res=-1;
for (int i=1;i<=n;++i) st[i].t=read(),st[i].c=read();
for (int i=log(INF)/log(2);i>=0;--i)
if (res+(1<<i)<=INF&&!check(res+(1<<i)))
res+=(1<<i);
res++,printf("%d\n",res==INF+1?-1:res);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7896kb
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: 22ms
memory: 7984kb
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'