QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608524 | #9427. Collect the Coins | Yzm007 | WA | 173ms | 6460kb | C++14 | 1.9kb | 2024-10-03 22:27:55 | 2024-10-03 22:27:55 |
Judging History
answer
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e6+10,INF=1e9,mod=998244353;
int t,n,isl[N];
P a[N];
map<int,int>q;
bool ok2(ll v,ll x){
ll now=-1,las=-1;
per(i,n,1){
if(a[i].se<=x || isl[i]){
if(now==-1 || abs(a[i].se-now)<=1ll*v*abs(a[i].fi-las))now=a[i].se,las=a[i].fi;
else return 0;
}
}
return 1;
}
bool ok(ll v){
ll l=1,r=1e9;
while(l<=r){
ll mid=(l+r)/2;
if(ok2(v,mid))l=mid+1;
else r=mid-1;
}
ll now=-1,las=-1;
per(i,n,1){
if(isl[i])continue;
if(a[i].se>=l){
if(now==-1 || abs(a[i].se-now)<=1ll*v*abs(a[i].fi-las))now=a[i].se,las=a[i].fi;
else return 0;
}
}
return 1;
}
ll sol(){
sci(n);
q.clear();
bool no=0;
rep(i,1,n){
isl[i]=0;
scanf("%lld%lld",&a[i].fi,&a[i].se);
q[a[i].fi]++;
if(q[a[i].fi]>=3)no=1;
}
if(no)return -1;
sort(a+1,a+n+1);
rep(i,1,n){
if(i+1<=n && a[i+1].fi==a[i].fi)isl[i]=1;
}
ll l=0,r=INF;
while(l<=r){
ll mid=(l+r)/2;
if(ok(mid))r=mid-1;
else l=mid+1;
}
if(l>INF)return -1;
return l;
}
int main(){
sci(t);
while(t--){
ptlle(sol());
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5980kb
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: 173ms
memory: 6460kb
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 1 6 0 3 2 2 0 4 5 0 1 5 1 2 0 0 0 1 4 2 0 2 1 3 0 5 2 3 2 6 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 2 0 1 4 4 3 0 0 2 2 6 4 5 1 0 0 1 0 3 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 4 3 0 3 3 3 5 ...
result:
wrong answer 6th lines differ - expected: '3', found: '1'