QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#743538 | #9738. Make It Divisible | zqx | WA | 1ms | 5664kb | C++14 | 1.3kb | 2024-11-13 19:26:42 | 2024-11-13 19:26:43 |
Judging History
你现在查看的是最新测评结果
- [2024-11-27 18:44:44]
- hack成功,自动添加数据
- (/hack/1263)
- [2024-11-14 09:10:13]
- hack成功,自动添加数据
- (/hack/1178)
- [2024-11-13 19:26:42]
- 提交
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[200010],b[200010],s[200010];
int n,k;
bool check(int x){
for(int i=1;i<=n;i++){
s[i]=a[i]+x;
}
stack<int>st;
for(int i=2;i<=n;i++){
if(s[i]%s[i-1]==0){
st.push(s[i]);
}else if(s[i-1]%s[i]==0){
while(st.empty()==0&&st.top()>s[i]){
if(st.top()%s[i]!=0)return false;
st.pop();
}
if(st.empty()==0&&s[i]%st.top()!=0)return false;
st.push(s[i]);
}else{
return false;
}
}
return true;
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int flag=0;
for(int i=1;i<=n;i++){
if(a[i]!=a[1]){
flag=i;
break;
}
}
if(!flag){
cout<<k<<" "<<(1+k)*k/2<<"\n";
return;
}
int res=0,resnum=0;
int num=abs(a[flag]-a[flag-1]);
vector<int>v;
for(int i=1;i*i<=num;i++){
if(num%i==0){
v.push_back(i);
if(num!=i*i){
v.push_back(num/i);
}
}
}
for(int i:v){
if(i>min(a[flag],a[flag-1])&&i-min(a[flag],a[flag-1])<=k){
if(check(i-min(a[flag],a[flag-1]))){
resnum++;
res+=i-min(a[flag],a[flag-1]);
}
}
}
cout<<resnum<<" "<<res<<"\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5632kb
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: -100
Wrong Answer
time: 1ms
memory: 5664kb
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:
1 1 0 0 1 1 1 1
result:
wrong answer 1st lines differ - expected: '0 0', found: '1 1'