QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608292#9427. Collect the CoinsYzm007WA 106ms4064kbC++141.8kb2024-10-03 20:27:302024-10-03 20:27:32

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-03 20:27:32]
  • 评测
  • 测评结果:WA
  • 用时:106ms
  • 内存:4064kb
  • [2024-10-03 20:27:30]
  • 提交

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;
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){
            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(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){
        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);
    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: 3792kb

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: 106ms
memory: 4064kb

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
-1
0
3
1
-1
6
0
3
2
2
0
4
5
0
1
-1
1
2
0
0
0
1
4
-1
0
2
1
-1
0
5
2
3
2
-1
-1
1
1
0
1
1
1
0
2
0
1
0
1
0
2
1
0
2
3
4
-1
1
1
1
0
1
-1
0
1
-1
4
3
0
0
2
2
6
-1
5
1
0
0
1
0
3
1
2
0
1
1
3
0
0
1
2
0
-1
0
2
2
2
1
0
0
0
5
1
2
0
-1
1
1
1
2
2
2
0
3
1
4
3
6
0
-1
1
1
-1
0
2
2
4
1
1
0
0
0
-1
2
2
1
0
0
-1
1
2
1
1...

result:

wrong answer 2nd lines differ - expected: '3', found: '-1'