QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#233491#5359. 面国建设xyz123100 ✓2115ms64196kbC++143.0kb2023-10-31 18:19:332023-10-31 18:19:33

Judging History

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

  • [2023-10-31 18:19:33]
  • 评测
  • 测评结果：100
  • 用时：2115ms
  • 内存：64196kb
查看
  • [2023-10-31 18:19:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,fac[1000001],inv[1000001],st[1000001],u[1000001],g[1000001];
char s[1000001];
struct p{long long q,w;}l[1000001];
long long pow_(long long qq,long long ww){long long ee=1;while(ww){if(ww&1) ee*=qq,ee%=mod;qq*=qq,qq%=mod,ww>>=1;}return ee%mod;}
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;}
void add(long long qq,long long ww){l[++o].q=ww,l[o].w=h[qq],h[qq]=o;}
long long gcd(long long qq,long long ww){return !ww?qq:gcd(ww,qq%ww);}
long long find(long long qq){return qq==fa[qq]?qq:fa[qq]=find(fa[qq]);}
void merge(long long qq,long long ww){long long f1=find(qq),f2=find(ww);if(f1==f2) return;fa[f1]=f2;}
long long C(long long qq,long long ww){return fac[qq]*inv[ww]%mod*inv[qq-ww]%mod;}
vector<long long> qu[1000001];
int main()
{
//	freopen("1.in","r",stdin);
	srand((unsigned)(time(0)^(*new int)));
	fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=pow_(fac[1000000],mod-2);for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	d[1]=2;g[1]=2;
	for(int i=2;i<=200000;i++)
	{
		d[i]=g[i]=1e9;
		for(int j=1;j<=i/2&&j<=200;j++)
		{
			g[i]=min(g[i],g[j]+g[i-j]);
		}
//		if(i<=200) cout<<i<<" "<<idd<<"\n";
		for(int j=1;j<=i/2&&j<=200;j++)
		{
			for(int k=0;k<qu[j].size();k++)
			{
				for(int m=0;m<qu[i-j].size();m++)
				{
					v[qu[j][k]+qu[i-j][m]]=1;
				}
			}
		}
		for(int j=1;j<i&&j<=200;j++)
		{
			for(int k=0;k<qu[i-j].size();k++)
			{
				for(int m=g[j];m<=j*2&&m+qu[i-j][k]<g[i];m++)
				{
					v[m+qu[i-j][k]]=1;
				}
			}
		}
		for(int j=1;j<i&&j<=200;j++)
		{
			for(int k=0;k<qu[j].size();k++)
			{
				for(int m=g[i-j];m<=(i-j)*2&&m+qu[j][k]<g[i];m++)
				{
					v[m+qu[j][k]]=1;
				}
			}
		}
		for(int j=sqrt(i);j>=1;j--)
		{
			if(i%j==0)
			{
				if(j+i/j<g[i]) v[j+i/j]=1;
			}
		}
		while(v[g[i]-1])
		{
			--g[i];v[g[i]]=0;
		}
		for(int j=1;j<g[i];j++) if(v[j]) qu[i].push_back(j),v[j]=0;
		for(int j=1;j<=i/2&&j<=200;j++)
		{
			for(int k=0;k<qu[j].size();k++)
			{
				for(int m=0;m<qu[i-j].size();m++)
				{
					v[qu[j][k]+qu[i-j][m]]=0;
				}
			}
		}
		for(int j=1;j<i&&j<=200;j++)
		{
			for(int k=0;k<qu[i-j].size();k++)
			{
				for(int m=g[j];m<=j*2&&m+qu[i-j][k]<=g[i];m++)
				{
					v[m+qu[i-j][k]]=0;
				}
			}
		}
		for(int j=1;j<i&&j<=200;j++)
		{
			for(int k=0;k<qu[j].size();k++)
			{
				for(int m=g[i-j];m<=(i-j)*2&&m+qu[j][k]<=g[i];m++)
				{
					v[m+qu[j][k]]=0;
				}
			}
		}
	}
//	cout<<g[200000];return 0;
	scanf("%lld%lld",&a,&b);b/=2;
	for(int i=1;i<=a;i++)
	{
		long long gg=min((long long)(i*2),b);
		if(gg>=g[i]) an+=gg-g[i]+1;
		for(int j=0;j<qu[i].size();j++)
		{
			if(qu[i][j]<=gg&&qu[i][j]<g[i]) ++an;
		}
	}
	printf("%lld",an);
	return 0;
}
源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

详细

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 2113ms
memory: 60400kb

input:

4 10

output:

7

result:

ok single line: '7'

Test #2:

score: 0
Accepted
time: 2108ms
memory: 61888kb

input:

7 2

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 2115ms
memory: 57360kb

input:

6 6

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 2105ms
memory: 61868kb

input:

10 7

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 2104ms
memory: 60532kb

input:

8 10

output:

8

result:

ok single line: '8'

Test #6:

score: 0
Accepted
time: 2103ms
memory: 61924kb

input:

10 8

output:

5

result:

ok single line: '5'

Subtask #2:

score: 12
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 12
Accepted
time: 2101ms
memory: 61792kb

input:

399 994

output:

125266

result:

ok single line: '125266'

Test #8:

score: 0
Accepted
time: 2097ms
memory: 59296kb

input:

742 645

output:

184225

result:

ok single line: '184225'

Test #9:

score: 0
Accepted
time: 2115ms
memory: 62184kb

input:

932 900

output:

328424

result:

ok single line: '328424'

Test #10:

score: 0
Accepted
time: 2103ms
memory: 57428kb

input:

943 971

output:

357500

result:

ok single line: '357500'

Test #11:

score: 0
Accepted
time: 2099ms
memory: 62160kb

input:

955 897

output:

335817

result:

ok single line: '335817'

Test #12:

score: 0
Accepted
time: 2102ms
memory: 61932kb

input:

903 971

output:

340678

result:

ok single line: '340678'

Test #13:

score: 0
Accepted
time: 2105ms
memory: 59792kb

input:

954 978

output:

364964

result:

ok single line: '364964'

Test #14:

score: 0
Accepted
time: 2106ms
memory: 58556kb

input:

908 902

output:

319849

result:

ok single line: '319849'

Test #15:

score: 0
Accepted
time: 2096ms
memory: 60884kb

input:

934 908

output:

332030

result:

ok single line: '332030'

Test #16:

score: 0
Accepted
time: 2106ms
memory: 59176kb

input:

961 924

output:

348391

result:

ok single line: '348391'

Subtask #3:

score: 31
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 31
Accepted
time: 2108ms
memory: 57292kb

input:

1951 2977

output:

2228950

result:

ok single line: '2228950'

Test #18:

score: 0
Accepted
time: 2103ms
memory: 60676kb

input:

4626 5415

output:

10254469

result:

ok single line: '10254469'

Test #19:

score: 0
Accepted
time: 2108ms
memory: 60484kb

input:

5983 4766

output:

12197679

result:

ok single line: '12197679'

Test #20:

score: 0
Accepted
time: 2099ms
memory: 59276kb

input:

5094 5425

output:

11472637

result:

ok single line: '11472637'

Test #21:

score: 0
Accepted
time: 2103ms
memory: 60504kb

input:

5598 4989

output:

11826716

result:

ok single line: '11826716'

Test #22:

score: 0
Accepted
time: 2100ms
memory: 60968kb

input:

5577 5188

output:

12208146

result:

ok single line: '12208146'

Test #23:

score: 0
Accepted
time: 2097ms
memory: 60788kb

input:

5688 5804

output:

13807758

result:

ok single line: '13807758'

Test #24:

score: 0
Accepted
time: 2102ms
memory: 60792kb

input:

5856 5309

output:

13161066

result:

ok single line: '13161066'

Test #25:

score: 0
Accepted
time: 2107ms
memory: 59728kb

input:

5378 5859

output:

13061554

result:

ok single line: '13061554'

Test #26:

score: 0
Accepted
time: 2102ms
memory: 59772kb

input:

5729 5635

output:

13554877

result:

ok single line: '13554877'

Subtask #4:

score: 51
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #27:

score: 51
Accepted
time: 2107ms
memory: 58692kb

input:

177004 361104

output:

23708315017

result:

ok single line: '23708315017'

Test #28:

score: 0
Accepted
time: 2087ms
memory: 60728kb

input:

165955 330686

output:

20513788444

result:

ok single line: '20513788444'

Test #29:

score: 0
Accepted
time: 2105ms
memory: 59044kb

input:

196341 379690

output:

28146877343

result:

ok single line: '28146877343'

Test #30:

score: 0
Accepted
time: 2105ms
memory: 57464kb

input:

157573 352489

output:

19921485073

result:

ok single line: '19921485073'

Test #31:

score: 0
Accepted
time: 2111ms
memory: 60568kb

input:

174981 388787

output:

24469285862

result:

ok single line: '24469285862'

Test #32:

score: 0
Accepted
time: 2096ms
memory: 62092kb

input:

179053 386583

output:

25166888234

result:

ok single line: '25166888234'

Test #33:

score: 0
Accepted
time: 2101ms
memory: 62072kb

input:

181239 344051

output:

23675514126

result:

ok single line: '23675514126'

Test #34:

score: 0
Accepted
time: 2090ms
memory: 59364kb

input:

194920 395575

output:

28656790378

result:

ok single line: '28656790378'

Test #35:

score: 0
Accepted
time: 2095ms
memory: 62248kb

input:

179011 399658

output:

25686628463

result:

ok single line: '25686628463'

Test #36:

score: 0
Accepted
time: 2105ms
memory: 57500kb

input:

183359 394921

output:

26352667541

result:

ok single line: '26352667541'

Test #37:

score: 0
Accepted
time: 2112ms
memory: 60844kb

input:

195360 389377

output:

28442072522

result:

ok single line: '28442072522'

Test #38:

score: 0
Accepted
time: 2107ms
memory: 57452kb

input:

191706 397710

output:

28122791775

result:

ok single line: '28122791775'

Test #39:

score: 0
Accepted
time: 2107ms
memory: 59700kb

input:

191762 396427

output:

28074496102

result:

ok single line: '28074496102'

Test #40:

score: 0
Accepted
time: 2099ms
memory: 59784kb

input:

197603 386515

output:

28732769430

result:

ok single line: '28732769430'

Test #41:

score: 0
Accepted
time: 2107ms
memory: 59144kb

input:

190189 377777

output:

26893005583

result:

ok single line: '26893005583'

Test #42:

score: 0
Accepted
time: 2107ms
memory: 61976kb

input:

189770 391031

output:

27434979251

result:

ok single line: '27434979251'

Test #43:

score: 0
Accepted
time: 2112ms
memory: 58716kb

input:

194039 389514

output:

28192735947

result:

ok single line: '28192735947'

Test #44:

score: 0
Accepted
time: 2097ms
memory: 62136kb

input:

197815 388430

output:

28870257334

result:

ok single line: '28870257334'

Test #45:

score: 0
Accepted
time: 2097ms
memory: 58612kb

input:

189687 383322

output:

27060812973

result:

ok single line: '27060812973'

Test #46:

score: 0
Accepted
time: 2105ms
memory: 64196kb

input:

196059 391296

output:

28672072117

result:

ok single line: '28672072117'
English 繁體中文 简体中文

服务器时间: 2024-11-30 09:44:41 | 开源项目