求调省选 D1T1
查看原帖
求调省选 D1T1
537046
大眼仔Happy楼主2024/3/7 21:00

rt,我把错误数据下载下来在本地过了,但是显示 WA 了,这是为啥。

#include<bits/stdc++.h>
using namespace std;
#define I __int128
const int N=1e5+5;
const I inf=1e36;
I inline read()
{
	I num=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
	return num*f;
}
void _print(I x){if(x>9)_print(x/10);putchar(x%10+'0');}
void print(I x){if(x<0)putchar('-'),x=-x;_print(x);putchar('\n');}
int T;I k,n,ans;
struct data
{
	I x,y;
	data friend operator +(const data A,const data B){return (data){A.x+B.x,A.y+B.y};}
	data friend operator -(const data A,const data B){return (data){A.x-B.x,A.y-B.y};}
}s,sP,p[N],eP;
#define Eset (node){inf,0}
#define Uset (node){0,inf}
struct node
{
	I l,r;
	node friend operator &(const node A,const node B)
	{
		if(A.l>A.r||B.l>B.r)return Eset;
		return (node){max(A.l,B.l),min(A.r,B.r)};
	}
};
node Ge(I k,I b)
{
	if(k<0)return (b<=0)?(node){0,b/k}:Eset;
	if(k>0)return (b<=0)?Uset:(node){b/k+(b%k!=0),inf};
	return (b<=0)?Uset:Eset;
}
node Le(I k,I b)
{
	if(k<0)return (b>=0)?Uset:(node){(b/k)+(b%k!=0),inf};
	if(k>0)return (b>=0)?(node){0,b/k}:Eset;
	return (b>=0)?Uset:Eset;
}
I calc(I id)
{
	I t=inf/n+1;node res=Uset;
	res=Le(s.x,eP.x)&Le(s.y,eP.y)&Ge(n*k+s.x+s.y,eP.x+eP.y-id*k);	if(res.l<=res.r)t=min(t,res.l);
	res=Le(s.x,eP.x)&Ge(s.y,eP.y)&Ge(n*k+s.x-s.y,eP.x-eP.y-id*k);	if(res.l<=res.r)t=min(t,res.l);
	res=Ge(s.x,eP.x)&Le(s.y,eP.y)&Ge(n*k-s.x+s.y,-eP.x+eP.y-id*k);	if(res.l<=res.r)t=min(t,res.l);
	res=Ge(s.x,eP.x)&Ge(s.y,eP.y)&Ge(n*k-s.x-s.y,-eP.x-eP.y-id*k);	if(res.l<=res.r)t=min(t,res.l);
	return t*n+id;
}
void solve()
{
	n=read();k=read();eP=(data){read(),read()};
	s=(data){0,0};ans=inf;
	for(int i=0;i<n;i++)s=s+(p[i]=(data){read(),read()});
	if(!eP.x&&!eP.y)return printf("0\n"),void();
	for(int i=0;i<n;i++)ans=min(ans,calc(i)),eP=eP-p[i];
	if(ans!=inf)print(ans);
	else printf("-1\n");
}
int main(){
//	freopen("P10217_1.in","r",stdin);
//	freopen("test.out","w",stdout);
	T=read();while(T--)solve();
	return 0;
}
2024/3/7 21:00
加载中...