QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#867364 | #9738. Make It Divisible | forget-star# | WA | 1ms | 3840kb | C++20 | 1.2kb | 2025-01-23 14:29:27 | 2025-01-23 14:29:29 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int n,k,a[N],b[N];
int l[N],r[N],st[N],top;
ll ans0,ans1;
void calc(ll x)
{
for(int i=1;i<=n;i++){
if(l[i]&&(a[l[i]]+x)%(a[i]+x)) return;
if(r[i]&&(a[r[i]]+x)%(a[i]+x)) return;
}
ans0++,ans1+=x;
return;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) l[i]=r[i]=0;ans0=ans1=top=0;
for(int i=1;i<=n;i++)
{
while(top>0&&a[st[top]]>a[i]) top--;
l[i]=r[st[top]];
r[st[top]]=i;
st[++top]=i;
}
for(int i=1;i<=n;i++) b[i]=a[i];
sort(b+1,b+n+1);
if(b[1]==b[n]) printf("%lld %lld\n",k,1ll*k*(k+1)/2);
else
{
ll mn=1e18,mx=0;
for(int i=1;i<=n;i++)
{
if(l[i]&&a[i]!=a[l[i]]) mn=a[i],mx=a[l[i]];
if(r[i]&&a[i]!=a[r[i]]) mn=a[i],mx=a[r[i]];
}
int x=mx-mn;
for(int i=1;1ll*i*i<=x;i++)
if(x%i==0)
{
if(i<=(k-mn)&&i>mn) calc(i-mn);
if(i!=x/i&&x/i<=(k-mn)&&x/i>mn) calc(x/i-mn);
}
printf("%lld %lld\n",ans0,ans1);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3840kb
input:
3 5 10 7 79 1 7 1 2 1000000000 1 2 1 100 1000000000
output:
3 8 0 0 100 5050
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
4 201 1000000000 1 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5...
output:
0 0 0 0 0 0 0 0
result:
ok 4 lines
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3840kb
input:
500 4 1000000000 8 14 24 18 4 1000000000 17 10 18 14 4 1000000000 6 17 19 19 4 1000000000 15 14 15 25 4 1000000000 16 16 5 25 4 1000000000 4 30 20 5 4 1000000000 11 4 23 9 4 1000000000 14 25 13 2 4 1000000000 18 18 1 15 4 1000000000 22 22 22 28 4 1000000000 15 17 17 10 4 1000000000 22 14 13 25 4 100...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 178th lines differ - expected: '1 2', found: '0 0'