QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#602628 | #9427. Collect the Coins | ucup-team3282 | WA | 24ms | 11996kb | C++14 | 2.0kb | 2024-10-01 11:20:59 | 2024-10-01 11:20:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int T;
int n;
int t[maxn],c[maxn];
bool f(int i,int j,int v){
if(j>i)
return 1;
return (ll)v*(t[i]-t[j])>=abs(c[i]-c[j]);
}
int fl[maxn],fr[maxn],b[maxn];
bool check(int v){
vector<int> il,ir;
for(int i=1;i<=n;i++)
fl[i]=fr[i]=b[i]=0;
for(int i=2;i<=n;i++){
if(!f(i,i-1,v)){
if(c[i]>c[i-1]){
if(b[i-1]==2||b[i]==1)
return 0;
b[i-1]=1;b[i]=2;
il.push_back(i-1);
ir.push_back(i);
}
else{
if(b[i-1]==1||b[i]==2)
return 0;
b[i]=1;b[i-1]=2;
il.push_back(i);
ir.push_back(i-1);
}
}
}
il.resize(unique(il.begin(),il.end())-il.begin());
ir.resize(unique(ir.begin(),ir.end())-ir.begin());
// cout<<"v: "<<v<<endl;for(int i:il)cout<<i<<' ';cout<<endl;for(int i:ir)cout<<i<<' ';cout<<endl;
if(il.size()<=1||ir.size()<=1)
return 1;
for(int k=1;k<il.size();k++){
int j=il[k-1],i=il[k];
if(!f(i,j,v))
return 0;
}
for(int k=1;k<ir.size();k++){
int j=ir[k-1],i=ir[k];
if(!f(i,j,v))
return 0;
}
for(int t=1;t<il[0];t++)
fl[t]=1;
for(int k=1;k<il.size();k++){
int j=il[k-1],i=il[k];
fl[j]=1;
for(int t=j+1;t<i;t++){
if(f(t,j,v)&&f(i,t,v))
fl[t]=1;
}
}
for(int t=il.back();t<=n;t++)
fl[t]=1;
for(int t=1;t<ir[0];t++)
fr[t]=1;
for(int k=1;k<ir.size();k++){
int j=ir[k-1],i=ir[k];
fr[j]=1;
for(int t=j+1;t<i;t++){
if(f(t,j,v)&&f(i,t,v))
fr[t]=1;
}
}
for(int t=ir.back();t<=n;t++)
fr[t]=1;
for(int i=1;i<=n;i++)
if(!fl[i]&&!fr[i])
return 0;
return 1;
}
int main(){
ios::sync_with_stdio(0);
cin>>T;
for(int _=1;_<=T;_++){
cin>>n;
for(int i=1;i<=n;i++)
cin>>t[i]>>c[i];
if(_==14){cout<<n<<endl;for(int i=1;i<=n;i++)cout<<t[i]<<' '<<c[i]<<endl;}
int l=0,r=1e9,mid,ans=-1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
if(T!=1135)
cout<<ans<<endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11724kb
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: 24ms
memory: 11996kb
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:
3 7 8 8 1 8 3
result:
wrong answer 1st lines differ - expected: '0', found: '3'