QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #575068 | #1465. Not Our Problem | sslwcr | WA | 9ms | 25208kb | C++14 | 2.3kb | 2024-09-19 10:18:00 | 2024-09-19 10:18:01 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
inline int read()
{
char c=getchar();
int ans=0,fl=1;
while ((c>'9'||c<'0')&&c!='-') c=getchar();
if (c=='-')
{
fl=-1;
}
else ans=c-'0';
c=getchar();
while (c<='9'&&c>='0')
{
ans=ans*10+c-'0';
c=getchar();
}
return ans*fl;
}
int n,k,a[500005],mx[500005],b[500005],sq;
int gt(int v)
{
if (v==0) return 4e18;
if (k/v/v>=v) return k/v/v;
return sqrt(k)/sqrt(v);
}
int s[1000006],f[1000006];
signed main()
{
n=read(),k=read();
sq=1;
while ((sq+1)*(sq+1)*(sq+1)<=k) sq++;
for (int i=1;i<=n;i++)
{
a[i]=read();
b[i]=a[i];
if (b[i]==-1) b[i]=0;
}
if (n==1&&a[1]==-1)
{
cout<<-1;
return 0;
}
if (n==1)
{
cout<<1;
return 0;
}
int ans=1;
for (int i=1;i<n;i++)
{
if (a[i]!=-1&&a[i+1]!=-1)
{
if (1.*a[i]*a[i+1]*min(a[i],a[i+1])>1e18)
{
printf("0");
return 0;
}
if (k<a[i]*a[i+1]*min(a[i],a[i+1]))
{
printf("0");
return 0;
}
continue;
}
}
for (int i=1;i<=n;i++)
{
if (a[i]==-1&&!b[i-1]&&!b[i+1])
{
printf("-1");
return 0;
}
}
for (int i=1;i<=sq;i++)
{
int y=k/(1LL*i*i);
s[i]=(s[i-1]+(y-sq+mod)%mod)%mod;
f[sq-i+1]=y;
}
for (int i=1;i<=n;i++)
{
if (a[i]!=-1)
{
continue;
}
if (a[i-1]!=-1&&a[i+1]!=-1)
{
int v=b[i-1];
mx[i]=gt(v);
v=b[i+1];
mx[i]=min(gt(v),mx[i]);
ans=ans*(1+mx[i]%mod)%mod;
continue;
}
int A=gt(a[i-1]),B=gt(a[i+2]);
int tmp=0;
if (A>sq&&B>sq)
{
int id=sq+1-(lower_bound(f+1,f+1+sq,A)-f);
tmp=(tmp+s[sq]-s[id]+mod+id*(A%mod-sq+mod)%mod)%mod;
id=sq+1-(lower_bound(f+1,f+1+sq,B)-f);
tmp=(tmp+s[sq]-s[id]+mod+id*(B%mod-sq+mod)%mod)%mod;
tmp=(tmp+sq*sq%mod)%mod;
tmp=(tmp+A+B+1)%mod;
}
else if (A<=sq&&B<=sq)
{
tmp=(1+A)*(1+B)%mod;
}
else
{
if (A>B) swap(A,B);
int id=sq+1-(lower_bound(f+1,f+1+sq,B)-f);
if(id>A)
{
tmp=(A%mod+1)*(B%mod+1)%mod;
}
else
{
tmp=(s[A]-s[id]+mod)%mod;
tmp=(tmp+(id+1)*(B%mod+1)%mod)%mod;
tmp=(tmp+(A-id)*(sq+1)%mod)%mod;
}
}
ans=ans*tmp%mod;
i++;
continue;
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9764kb
input:
4 100 -1 7 2 -1
output:
104
result:
ok 1 number(s): "104"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
4 100 10 -1 -1 1
output:
240
result:
ok 1 number(s): "240"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7628kb
input:
1 0 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7776kb
input:
2 10 10 10
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 9828kb
input:
7 1000 -1 25 0 388 -1 -1 1
output:
14014
result:
ok 1 number(s): "14014"
Test #6:
score: 0
Accepted
time: 1ms
memory: 9808kb
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: 4ms
memory: 25208kb
input:
7 1000000000000000000 -1 193562447565998153 0 10833 -1 -1 12700
output:
429385005
result:
ok 1 number(s): "429385005"
Test #8:
score: 0
Accepted
time: 0ms
memory: 9736kb
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: 7696kb
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: 9ms
memory: 25120kb
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: -100
Wrong Answer
time: 4ms
memory: 14316kb
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:
0
result:
wrong answer 1st numbers differ - expected: '104236068', found: '0'