骗分程序求助
查看原帖
骗分程序求助
846661
ARIS1_0楼主2024/10/10 19:32

别给我正解,我在练习骗分,请从骗分的角度来调试我的程序

目标:sub0 sub1 sub2

期望:42pts

实际:10pts(sub2 AC)

ll n,f,d[100005],m,anspos,ans=INT_MAX,x,y,z,l,r=1e12;
bool vis[100005];
const int mod=1e9;
bool check(ll x,ll st){
	memset(vis,0,sizeof(vis));
	ll a=x;
	for(int i=st;;i++){
		if(vis[i])break;
		vis[i]=1;
		if(i>=n){
			if(a>=d[n]){
				i=1;
				a++;
				continue;
			}else return 0;
		}
		if(a>=d[i]){
			a++;
			continue;
		}
		return 0;
	}
	return 1;
}
ll solve(ll pos){
	l=0,r=1e12;
	ll ret=0;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(mid,pos))ret=mid,r=mid-1;
		else l=mid+1;
	}
	return ret;
}
int main(){
	n=read();f=read();
	if(f==1)for(int i=1;i<=n;i++)d[i]=read();
	else{
		m=read();x=read();y=read();z=read();
		for(int i=1;i<=m;i++)d[i]=read();
		for(int i=m+1;i<=n;i++){
			d[i]=((x*d[i-2]+y*d[i-1]+z)%mod)+1;
		}
	}
	if(n<=6000){//sub0 1
		for(int i=1;i<=n;i++){
			ll tmp=solve(i);
			if(tmp<ans){
				ans=tmp;
				anspos=i;
			}
		}
		cout<<ans<<' '<<anspos;
		return 0;
	}
	ll ans=solve(1);//sub2
	cout<<ans<<" 1";
	return 0;
}
2024/10/10 19:32
加载中...