省选 D1T1 求调
  • 板块学术版
  • 楼主Coffee_zzz/xin
  • 当前回复9
  • 已保存回复9
  • 发布时间2024/3/2 21:43
  • 上次更新2024/3/2 21:55:09
查看原帖
省选 D1T1 求调
744687
Coffee_zzz/xin楼主2024/3/2 21:43

熨斗 40pts,似乎是数据类型的问题。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int mod=998244353,N=1e5+5,inf=8e13;
int x[N],y[N],p[N],q[N];
struct Nod{
    /*>= 1  <= 0*/
    int p,q,f;
}nod[5],t[5];
bool judgel(int a,int b,int c,int d){
    bool res=0;
    if(b<0) res^=1;
    if(d<0) res^=1;
    __int128 l=a*d,r=b*c;
    if(res==0&&l<=r) return 1;
    if(res==1&&l>=r) return 1;
    return 0;
}
bool judger(int a,int b,int c,int d){
    if(b==0) return 1;
    bool res=1;
    if(b<0) res^=1;
    if(d<0) res^=1;
    __int128 l=a*d,r=b*c;
    if(res==0&&l<=r) return 1;
    if(res==1&&l>=r) return 1;
    return 0;
}
int check(Nod a,Nod b,Nod c){
    t[0]=a,t[1]=b,t[2]=c;
    int cnt=0,lp=0,lq=1,rp=0,rq=0;
    for(int i=0;i<3;i++){
        if(t[i].q==0){
            if(t[i].f==0&&t[i].p>0) return inf;
            if(t[i].f==1&&t[i].p<0) return inf;
        }
        else{
            if(t[i].q<0) nod[cnt++]={t[i].p,t[i].q,t[i].f^1};
            else nod[cnt++]=t[i];
        }
    }
    for(int i=0;i<cnt;i++){
        if(nod[i].f==0){
            if(judgel(lp,lq,nod[i].p,nod[i].q)) lp=nod[i].p,lq=nod[i].q;
        }
        else{
            if(judger(rp,rq,nod[i].p,nod[i].q)) rp=nod[i].p,rq=nod[i].q;
        }
    }
    if(rp<0) rp*=-1,rq*=-1;
    if(rq<0) return inf;
    int l=(lp+lq-1)/lq;
    if(rq==0) return l;
    int r=rp/rq;
    if(l<=r) return l;
    else return inf;
}
void solve(){
    int n,k,a,b,ans=8e18;
    cin>>n>>k>>a>>b;
    for(int i=0;i<n;i++) cin>>x[i]>>y[i];
    p[0]=x[0],q[0]=y[0];
    for(int i=1;i<n;i++) p[i]=p[i-1]+x[i],q[i]=q[i-1]+y[i];
    for(int f=0;f<n;f++){
        int c=a,d=b;
        if(f!=0) c=c-p[f-1],d=d-q[f-1];
        ans=min(ans,check({c,p[n-1],1},{d,q[n-1],1},{c+d-k*f,k*n+p[n-1]+q[n-1],0})*n+f);
        ans=min(ans,check({c,p[n-1],1},{d,q[n-1],0},{c-d-k*f,k*n+p[n-1]-q[n-1],0})*n+f);
        ans=min(ans,check({c,p[n-1],0},{d,q[n-1],1},{-c+d-k*f,k*n-p[n-1]+q[n-1],0})*n+f);
        ans=min(ans,check({c,p[n-1],0},{d,q[n-1],0},{-c-d-k*f,k*n-p[n-1]-q[n-1],0})*n+f);
    }
    if(ans<inf) cout<<ans<<endl;
    else cout<<-1<<endl;
}
signed main(){
    freopen("wind.in","r",stdin);
    freopen("wind.out","w",stdout);
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}
2024/3/2 21:43
加载中...