QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797781#7963. 多折较差验证tensai_xnnWA 0ms3924kbC++201.1kb2024-12-03 18:13:322024-12-03 18:13:33

Judging History

你现在查看的是最新测评结果

  • [2024-12-03 18:13:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3924kb
  • [2024-12-03 18:13:32]
  • 提交

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'