QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#797781 | #7963. 多折较差验证 | tensai_xnn | WA | 0ms | 3924kb | C++20 | 1.1kb | 2024-12-03 18:13:32 | 2024-12-03 18:13:33 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define hachimi cat
#define oukinkin milktea
#define bacon maozedong
#define my_son dengxiaoping
#define winnie xijinping
#define _5t5 xijinping
#define sensai xijinping
#pragma GCC optimize(2)
#pragma GCC optimize("inline")
using namespace std;
int n,k;
string s;
int dp[200005];
int stp[200005];
int cal(int x){
for(int i=2;i<=n;i++){
stp[i]=stp[i-1];
if(s[i]=='0'){
dp[i]=dp[i-1]-stp[i];
}
else{
stp[i]+=(i<=x?1:0);
dp[i]=dp[i-1]+stp[i];
}
}
return (dp[n]>=k);
}
int bin_sch(int l,int r){
while(l<r){
int mid=(l+r)/2;
if(cal(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cal(l);
return stp[n]+1;
}
int main(){
std::ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--){
cin>>n>>k>>s;s=' '+s;
/*for(int i=1;i<=n;i++){
cal(i);
for(int j=1;j<=n;j++){
cout<<stp[j]<<' ';
}cout<<endl;
}*/
cal(n);
int ans;
if(stp[n]+1>=k){
ans=bin_sch(1,n);
}
else{
ans=-1;
}
cout<<"ans=";
cout<<ans<<endl;
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3924kb
input:
5000 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...
output:
ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ans=1 ...
result:
wrong answer 1st lines differ - expected: '5000 12497500', found: 'ans=1'