1 / 5
Sep 2019

I’m getting WA on FRSCR, but I have compared it to a brute program without finding any bug.
I use a binary search for this question.
I can’t check it on Toolkit, so help me please.
Solution is below.

c++(g++ 4.3.2)

#include<bits/stdc++.h>
#define int long long
using namespace std;

#define dd ch=getchar()
inline int read()
{
int x=0;char dd;bool f=false;
while(!isdigit(ch))f|=ch==’-’,dd;
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
return f?-x:x;
}
#undef dd
void write(int x)
{
if(x<0)x=-x,putchar(’-’);
if(x>9)write(x/10);
putchar(x%10+48);
}

const int N=105,P=1e6+100;

int p,n,m;
int a[N],b[N];
int sum[P],tot=0;

int ans,res;
inline int calc(int mid)
{
ans=0,res=0;
for(int i=1;i<=n;i++)
{
int id=upper_bound(sum+1,sum+1+tot,mid/a[i])-sum-1;
if(id>tot)continue;
// while(sum[id]*a[i]<mid)id++;
// while(sum[id]*a[i]>mid)id–;
ans+=id;
}
mid=p-mid;
for(int i=1;i<=m;i++)
{
int id=upper_bound(sum+1,sum+1+tot,mid/b[i])-sum-1;
if(id>tot)continue;
// while(sum[id]*b[i]<mid)id++;
// while(sum[id]*b[i]>mid)id–;
res+=id;
}
return min(res,ans);
}

inline void sol()
{
int l=0,r=p+1;
while(r-l>1)
{
int mid=(l+r)>>1;
calc(mid);
if(ans<=res)l=mid;
else r=mid;
}
int final_ans=calc(l);
r=p;
while(r-l>1)
{
int mid=(l+r)>>1;
calc(mid);
if(ans>=res)r=mid;
else l=mid;
}
final_ans=max(final_ans,calc®);
write(final_ans);putchar(’\n’);
}

signed main()
{
freopen(“cr.in”,“r”,stdin);
freopen(“cr.out”,“w”,stdout);
int T=read();
for(int i=1;;i++)
{
sum[i]=sum[i-1]+i;
if(sum[i]>2e9){tot=i-1;break;}
}
while(T–)
{
p=read(),n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)b[i]=read();
sol();
}
return 0;
}

And here is my brute program.

#include<bits/stdc++.h>
#define re register
using namespace std;

#define dd ch=getchar()
inline int read()
{
int x=0;char dd;bool f=false;
while(!isdigit(ch))f|=ch==’-’,dd;
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
return f?-x:x;
}
#undef dd
void write(int x)
{
if(x<0)x=-x,putchar(’-’);
if(x>9)write(x/10);
putchar(x%10+48);
}

const int N=105;

int n,m,p;
int a[N],b[N];

inline int calc(int mid)
{
int ans=0,res=0;
for(int i=1;i<=n;i++)
for(re int pos=a[i],sum=a[i];pos<=mid;sum+=a[i],pos+=sum)
ans++;
mid=p-mid;
for(int i=1;i<=m;i++)
for(re int pos=b[i],sum=b[i];pos<=mid;sum+=b[i],pos+=sum)
res++;
return min(ans,res);
}

inline void sol()
{
int ans=0;
for(int i=1;i<=p;i++)
ans=max(ans,calc(i));
write(ans),putchar(’\n’);
}

int main()
{
freopen(“cr.in”,“r”,stdin);
freopen(“std.out”,“w”,stdout);
int T=read();
while(T–)
{
p=read(),n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)b[i]=read();
sol();
}
return 0;
}

(Forgive me for my bad English because I am talking to you with a translator.)

  • created

    Sep '19
  • last reply

    Sep '19
  • 4

    replies

  • 640

    views

  • 2

    users

  • 2

    links

my program.

#include<bits/stdc++.h>
#define int long long
using namespace std;

#define dd ch=getchar()
inline int read()
{
	int x=0;char dd;bool f=false;
	while(!isdigit(ch))f|=ch=='-',dd;
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
	return f?-x:x;
}
#undef dd
void write(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+48);
}

const int N=105,P=1e6+100;

int p,n,m;
int a[N],b[N];
int sum[P],tot=0;

int ans,res;
inline int calc(int mid)
{
	ans=0,res=0;
	for(int i=1;i<=n;i++)
	{
		int id=upper_bound(sum+1,sum+1+tot,mid/a[i])-sum-1;
		if(id>tot)continue;
//		while(sum[id]*a[i]<mid)id++;
//		while(sum[id]*a[i]>mid)id--;
		ans+=id;
	}
	mid=p-mid;
	for(int i=1;i<=m;i++)
	{
		int id=upper_bound(sum+1,sum+1+tot,mid/b[i])-sum-1;
		if(id>tot)continue;
//		while(sum[id]*b[i]<mid)id++;
//		while(sum[id]*b[i]>mid)id--;
		res+=id;
	}
	return min(res,ans);
}

inline void sol()
{
	int l=0,r=p+1;
	while(r-l>1)
	{
		int mid=(l+r)>>1;
		calc(mid);
		if(ans<=res)l=mid;
		else r=mid;
	}
	int final_ans=calc(l);
	r=p;
	while(r-l>1)
	{
		int mid=(l+r)>>1;
		calc(mid);
		if(ans>=res)r=mid;
		else l=mid;
	}
	final_ans=max(final_ans,calc(r));
	write(final_ans);putchar('\n');
}

signed main()
{
	freopen("cr.in","r",stdin);
	freopen("cr.out","w",stdout);
	int T=read();
	for(int i=1;;i++)
	{
		sum[i]=sum[i-1]+i;
		if(sum[i]>2e9){tot=i-1;break;}
	}
	while(T--)
	{
		p=read(),n=read(),m=read();
		for(int i=1;i<=n;i++)a[i]=read();
		for(int i=1;i<=m;i++)b[i]=read();
		sol();
	}
	return 0;
}

brute

#include<bits/stdc++.h>
#define re register
using namespace std;

#define dd ch=getchar()
inline int read()
{
	int x=0;char dd;bool f=false;
	while(!isdigit(ch))f|=ch=='-',dd;
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
	return f?-x:x;
}
#undef dd
void write(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+48);
}

const int N=105;

int n,m,p;
int a[N],b[N];

inline int calc(int mid)
{
	int ans=0,res=0;
	for(int i=1;i<=n;i++)
		for(re int pos=a[i],sum=a[i];pos<=mid;sum+=a[i],pos+=sum)
			ans++;
	mid=p-mid;
	for(int i=1;i<=m;i++)
		for(re int pos=b[i],sum=b[i];pos<=mid;sum+=b[i],pos+=sum)
			res++;
	return min(ans,res);
}

inline void sol()
{
	int ans=0;
	for(int i=1;i<=p;i++)
		ans=max(ans,calc(i));
	write(ans),putchar('\n');
}

int main()
{
	freopen("cr.in","r",stdin);
	freopen("std.out","w",stdout);
	int T=read();
	while(T--)
	{
		p=read(),n=read(),m=read();
		for(int i=1;i<=n;i++)a[i]=read();
		for(int i=1;i<=m;i++)b[i]=read();
		sol();
	}
	return 0;
}

And you did remove these lines before you submitted?

FRSCR2