QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#35404 | #1465. Not Our Problem | PineAppleblue17 | WA | 239ms | 22148kb | C++14 | 1.2kb | 2022-06-15 22:07:32 | 2022-06-15 22:07:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long N=2e6+5,mod=998244353,inv2=(mod+1)/2;
long long n,C,ans=1,LIM;
long long a[N],s[N];
long long getlim(long long a){
if(!a) return C;
return max(C/a/a,(long long)sqrt(C/a));
}
long long S(long long x){
return x*(x+1)%mod*inv2%mod;
}
long long cal(long long p,long long q){
long long L=min(min(p,q),LIM),lim=min(L,(long long)sqrt(C/q));
long long tot=(q+1+L+q*lim%mod+mod-S(lim)+s[L]+mod-s[lim])%mod;
return tot;
}
int main(){
cin>>n>>C;
while(LIM+1<=C/(LIM+1)/(LIM+1)) LIM++;
for(int i=1;i<=LIM;i++) s[i]=(s[i-1]+(C/i/i-i))%mod;
for(long long i=1;i<=n;i++) cin>>a[i];
for(long long l=0,r;l<=n;l=r){
r=l+1;
while(a[r]==-1) r++;
if(r-l+(!a[l])+(!a[r])>3) return puts("-1"),0;
if(r-l==1){
if(a[l] && a[r] && min(a[l],a[r])>C/a[l]/a[r]) return puts("0"),0;
else continue;
}
long long x=getlim(a[l]),y=getlim(a[r]);
if(r-l==2){
ans=ans*(min(x,y)+1)%mod;
continue;
}
if(r-l==3){
if(!x){
ans=ans*(y+1)%mod;
continue;
}
if(!y){
ans=ans*(x+1)%mod;
continue;
}
long long tot=min(min(x,y),LIM)+1;
ans=ans*(cal(x,y)+cal(y,x)+mod-tot)%mod;
}
}
cout<<ans;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5608kb
input:
4 100 -1 7 2 -1
output:
104
result:
ok 1 number(s): "104"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5680kb
input:
4 100 10 -1 -1 1
output:
240
result:
ok 1 number(s): "240"
Test #3:
score: 0
Accepted
time: 3ms
memory: 5688kb
input:
1 0 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 3ms
memory: 5476kb
input:
2 10 10 10
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 3ms
memory: 5604kb
input:
7 1000 -1 25 0 388 -1 -1 1
output:
14014
result:
ok 1 number(s): "14014"
Test #6:
score: 0
Accepted
time: 2ms
memory: 5704kb
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: 32ms
memory: 13568kb
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: 5636kb
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: 2ms
memory: 5576kb
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: 35ms
memory: 13592kb
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: 162ms
memory: 13868kb
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: 179ms
memory: 11748kb
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: -100
Wrong Answer
time: 239ms
memory: 22148kb
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:
80853357
result:
wrong answer 1st numbers differ - expected: '727350500', found: '80853357'