QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#820076#1465. Not Our ProblemcwfxlhWA 94ms34860kbC++141.7kb2024-12-18 19:27:262024-12-18 19:27:33

Judging History

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

  • [2024-12-18 19:27:33]
  • 评测
  • 测评结果:WA
  • 用时:94ms
  • 内存:34860kb
  • [2024-12-18 19:27:26]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define MOD 998244353
using namespace std;
int n,c,a[1000003],f[1000003],pre[1000003],ans=1,lmt[1000003],gg;
bool chk(int X,int Y){
	if(X>Y)swap(X,Y);
	if(X>1000000)return false;
	if(X==0||Y==0)return true;
	if((c/(X*X))<Y)return false;
	return true;
}
int calc(int X){
	if(X==0)return c;
	if(chk(X,X))return f[X];
	return (int)(sqrt(c/X));
}
int getsum(int l,int r){return ((r-l+1)%MOD)*(((l+r)%MOD)*((MOD+1)/2)%MOD)%MOD;}
int lft,rgt,mid;
int getnum(int X,int Y){
	X=min(X,Y);
	X=min(X,gg);
	int ret=0;
	lft=0;
	rgt=X;
	while(lft<rgt){
		mid=((lft+rgt)>>1)+1;
		if(f[mid]>=Y)lft=mid;
		else rgt=mid-1;
	}
	ret=((Y%MOD)*((lft+1)%MOD)-getsum(-1,lft-1))%MOD;
	ret=(ret+pre[X]-pre[lft])%MOD;
	return ret;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>c;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		if(a[i]==-1&&((i==1)||(a[i-1]==0)||(a[i-1]==-1))&&((i==n)||(a[i+1]==0)||(a[i+1]==-1))){
			cout<<-1;
			return 0;
		}
	}
	for(int i=1;i<=1000000;i++){
		if(i*i*i>c)f[i]=i-1;
		else f[i]=(c/(i*i));
		if(i*i*i<=c)gg=i;
		pre[i]=(pre[i-1]+f[i]-i+1)%MOD;
	}
	f[0]=c;
	for(int i=1;i<=n;i++)lmt[i]=c;
	for(int i=1;i<n;i++){
		if(a[i]!=-1&&a[i+1]!=-1&&(!chk(a[i],a[i+1]))){
			cout<<0;
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]!=-1){
			if(i>1)lmt[i-1]=min(lmt[i-1],calc(a[i]));
			if(i<n)lmt[i+1]=min(lmt[i+1],calc(a[i]));
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]!=-1)continue;
		if(i==n||a[i+1]!=-1){
			ans=ans*((lmt[i]+1)%MOD)%MOD;
			continue;
		}
		ans=ans*((getnum(lmt[i],lmt[i+1])+getnum(lmt[i+1],lmt[i])-min(min(lmt[i],lmt[i+1]),gg)-1)%MOD)%MOD;
		i++;
	}
	ans%=MOD;
	ans+=MOD;
	ans%=MOD;
	cout<<ans;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 19756kb

input:

4 100
-1 7 2 -1

output:

104

result:

ok 1 number(s): "104"

Test #2:

score: 0
Accepted
time: 7ms
memory: 20984kb

input:

4 100
10 -1 -1 1

output:

240

result:

ok 1 number(s): "240"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5788kb

input:

1 0
-1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 20696kb

input:

2 10
10 10

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 19548kb

input:

7 1000
-1 25 0 388 -1 -1 1

output:

14014

result:

ok 1 number(s): "14014"

Test #6:

score: 0
Accepted
time: 3ms
memory: 20492kb

input:

10 1000000
-1 71350 0 6 -1 2 2 -1 -1 358968

output:

652782809

result:

ok 1 number(s): "652782809"

Test #7:

score: 0
Accepted
time: 7ms
memory: 20216kb

input:

7 1000000000000000000
-1 193562447565998153 0 10833 -1 -1 12700

output:

429385005

result:

ok 1 number(s): "429385005"

Test #8:

score: 0
Accepted
time: 3ms
memory: 20644kb

input:

100 1000
-1 174 2 -1 -1 1 2 -1 -1 2 139 -1 -1 1 4 -1 -1 1 1 -1 -1 4 18 -1 -1 356 1 -1 -1 31 1 -1 -1 1 2 -1 -1 1 7 -1 -1 2 0 509 -1 -1 174 0 22 -1 -1 1 1 -1 -1 801 0 2 -1 -1 6 2 -1 -1 1 23 -1 -1 446 0 927 -1 -1 635 1 -1 -1 513 0 5 -1 -1 2 6 -1 -1 2 1 -1 -1 839 0 342 -1 -1 8 1 -1 -1 2

output:

240069117

result:

ok 1 number(s): "240069117"

Test #9:

score: 0
Accepted
time: 0ms
memory: 21004kb

input:

100 1000000
2 -1 -1 257208 1 -1 -1 80 14 -1 -1 20 113 -1 -1 2 155991 -1 -1 1 805463 -1 -1 734 1 -1 -1 942182 0 3 -1 -1 1 1 -1 -1 3 88674 -1 -1 718 0 793 -1 -1 540 1 -1 -1 1 893042 -1 -1 891 0 491 -1 -1 6 18 -1 -1 1 735332 -1 -1 1 1 -1 -1 231702 0 22 -1 -1 1 476 -1 -1 826 20 -1 -1 1 29 -1 -1 2 989 -1...

output:

279593366

result:

ok 1 number(s): "279593366"

Test #10:

score: 0
Accepted
time: 3ms
memory: 20240kb

input:

97 1000000000000000000
-1 55 1 -1 -1 844479880 0 123881535849416001 -1 -1 128083297778537531 1 -1 -1 171572811 0 352900396625380054 -1 -1 1 1 -1 -1 41 6 -1 -1 21627 155 -1 643122694 0 392322295 -1 -1 254987357 2 -1 -1 4 0 571457328786259212 -1 -1 1 8816 -1 -1 131254846109630352 0 971779784498766346 ...

output:

188490398

result:

ok 1 number(s): "188490398"

Test #11:

score: 0
Accepted
time: 54ms
memory: 34800kb

input:

999998 1000
-1 343 1 -1 -1 1 3 -1 -1 1 1 -1 -1 2 0 468 -1 -1 1 1 -1 -1 783 0 5 -1 -1 2 0 760 -1 -1 318 1 -1 -1 1 320 -1 -1 27 1 -1 -1 2 2 -1 -1 2 1 -1 -1 997 1 -1 -1 547 0 313 -1 -1 4 0 304 -1 -1 1 4 -1 -1 980 0 96 -1 -1 1 797 -1 -1 13 0 13 -1 -1 19 0 401 -1 -1 1 1 -1 -1 5 5 -1 -1 26 0 458 -1 -1 6 0...

output:

104236068

result:

ok 1 number(s): "104236068"

Test #12:

score: 0
Accepted
time: 67ms
memory: 34860kb

input:

999998 1000000
-1 538406 1 -1 -1 1 2 -1 -1 288 0 393 -1 -1 256582 0 111893 -1 1 1 -1 -1 105454 0 40 -1 -1 1 4 -1 -1 6 1 -1 -1 3 0 588226 -1 -1 2 22 -1 -1 1 477043 -1 -1 2 912 -1 -1 3 0 539669 -1 -1 1 1 -1 -1 597 0 423 -1 -1 717193 0 506800 -1 -1 424362 0 523732 -1 -1 411789 0 2 -1 -1 2 0 681371 -1 -...

output:

945384981

result:

ok 1 number(s): "945384981"

Test #13:

score: 0
Accepted
time: 94ms
memory: 34840kb

input:

999999 1000000000000000000
34 -1 -1 10403 0 945252394656439232 -1 -1 11 3 -1 -1 2789 153814328 -1 -1 685484514683924741 1 -1 -1 1 14600 -1 -1 162108378 0 942407706831037158 -1 -1 1 81 -1 -1 286801961 1 -1 -1 13177 356030442 -1 -1 9557 0 647686052355282463 -1 -1 797322887 0 33989350 -1 -1 31337243480...

output:

727350500

result:

ok 1 number(s): "727350500"

Test #14:

score: -100
Wrong Answer
time: 1ms
memory: 5604kb

input:

50 1000
-1 -1 -1 694 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 555 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

-1

result:

wrong answer 1st numbers differ - expected: '0', found: '-1'