QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#727992#5983. Pretty Good ProportionBigJoker0 2300ms44732kbC++141.1kb2024-11-09 14:19:212024-11-09 14:19:55

Judging History

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

  • [2024-11-09 14:19:55]
  • 评测
  • 测评结果:0
  • 用时:2300ms
  • 内存:44732kb
  • [2024-11-09 14:19:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n;
int a[N],sx[N],sy[N];
double f[N],p;
set<pair<double,int> >S;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int _;
	cin>>_;
	while(_--){
		cin>>n>>p;
		for(int i=1;i<=n;i++){
			char x;
			cin>>x;
			a[i]=x-'0';
			sx[i]=sx[i-1]+a[i];
			sy[i]=sy[i-1]+1;
		}
		for(int i=0;i<=n;i++)
			f[i]=sx[i]-p*sy[i];
//		for(int i=1;i<=n;i++)
//			cout<<fixed<<setprecision(6)<<f[i]<<'\n';
		S.clear();
		double ans=1e9;
		int al=n;
		for(int i=n;i;i--){
			S.insert(make_pair(f[i],i));
			auto R=S.upper_bound(make_pair(f[i-1],114514)),L=R;
			if(R!=S.end()){
				int l=i,r=(*R).second;
				double ret=(sx[r]-sx[l-1])/1.0/(sy[r]-sy[l-1]);
				if(fabs(ret-p)<=fabs(ans-p)){
					ans=ret;
					al=l;
				}
			}
			if(R!=S.begin()){
				L--;
				int l=i,r=(*L).second;
				double ret=(sx[r]-sx[l-1])/1.0/(sy[r]-sy[l-1]);
				if(fabs(ret-p)<=fabs(ans-p)){
					ans=ret;
					al=l;
				}
			}
		}
		cout<<al<<'\n';
	}
	return 0;
}
/*
1
7 0.5
1101110

4
7 0.5
1101110
11 0.8
11111011110
9 0.75
011001011
9 0.666
010111100
*/

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 5960kb

input:

100
10 0.827672
0010101011
4 0.932623
0100
1000 0.834002
011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...

output:

7
2
11
1
1
2
1
1
1
1
1
5
6
565
1
1
1
1
1
1
1
1
1
845
1
1
2
156
1
1
1
1
1
1
394
2
174
1
3
1
131
4
1
841
2
6
1
1
75
1
2
1
1
1
1
1
2
1
2
1
1
1
9
1
1
839
3
3
1
1
1
613
1
6
1
1
1
1
1
1
2
1
321
1
1
7
80
1
1
1
1
1
2
1
2
159
1
1
4
1

result:

wrong answer 1st lines differ - expected: 'Case #1: 6', found: '7'

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 2300ms
memory: 44732kb

input:

100
15 0.333333
000000000011000
10 0.418754
0101100001
2 0.499999
01
3 0.977951
001
2 0.249999
01
10 0.670229
0111011001
1000 0.500001
001101111110110010110000010010110001110010001101110111010011000010100011011101010110011011011010111110011100011000001000101011100011010100101101111110100101011010111...

output:

7
1
1
3
1
1
1
1
1
1
1
1
1
1
1
4334
1
1
124
1
1
1
1
1
1
1
1
4
1
682
1
1
3
1
1
1
1
1
2
3
1
289
3
2
2
1
1
1
1
1
1
1
1
2
1
2
1
6
6
1
2
2
1
3
2
1
7
4
1
501
2
1
1
2
1
2
189
4
1
7
499839
1
1
6
1
1
1
499841
1
1
9
5
1
2
1
1
1
93
1
1

result:

wrong answer 1st lines differ - expected: 'Case #1: 6', found: '7'