QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#877551 | #9738. Make It Divisible | xieliren | WA | 0ms | 3584kb | C++23 | 1.6kb | 2025-01-31 23:19:16 | 2025-01-31 23:19:20 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int read(){
int s = 0, f = 1;char ch = getchar();
while(!isdigit(ch)){if(ch == '-')f = -1;ch = getchar();}
while(isdigit(ch)){s = s * 10 + ch - '0';ch = getchar();}
return s * f;
}
void write(int x){
if(x < 0){putchar('-'); x = -x;}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int MAXN = 5e4 + 5;
int t, n, k, top, cnt, a[MAXN], ls[MAXN], rs[MAXN], stk[MAXN], minn;
LL res;
bool check(int rt, int x){
if(!rt)return 1;
if(ls[rt] && ((a[ls[rt]] + x) % (a[rt] + x) != 0))return 0;
if(rs[rt] && ((a[rs[rt]] + x) % (a[rt] + x) != 0))return 0;
return check(ls[rt], x) && check(rs[rt], x);
}
void check2(int x){
if(x > k || x < 1)return ;
if(check(stk[1], x))cnt ++, res += x;
}
int main(){
t = read();
while(t --){
n = read(), k = read();
cnt = res = top = 0;
for(int i = 0;i <= n;i ++)ls[i] = rs[i] = stk[i] = 0;
top = 0;
for(int i = 1;i <= n;i ++){
a[i] = read();
while(top && a[stk[top]] > a[i])top --;
ls[i] = rs[stk[top]];
rs[stk[top]] = i;
stk[++ top] = i;
}
bool flag = 1;
for(int i = 1;i <= n;i ++)flag &= (a[i] == a[1]);
if(flag){
printf("%d %lld\n", k, 1ll * k * (k + 1) / 2);
continue;
}
int tmp = 0;minn = 0;
for(int i = 1;i <= n;i ++){
if(ls[i] && !tmp)
tmp = a[ls[i]] - a[i], minn = a[i];
else if(rs[i] && !tmp)
tmp = a[rs[i]] - a[i], minn = a[i];
}
return 0;
for(int i = 1;i * i <= tmp;i ++){
if(tmp % i == 0){
if(i * i != tmp)check2(i - minn);
check2(tmp / i - minn);
}
}
printf("%d %lld\n", cnt, res);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
3 5 10 7 79 1 7 1 2 1000000000 1 2 1 100 1000000000
output:
result:
wrong answer 1st lines differ - expected: '3 8', found: ''