QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345106#8242. V-Diagramoscaryang#WA 1ms5872kbC++201.2kb2024-03-06 08:43:262024-03-06 08:43:26

Judging History

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

  • [2024-03-06 08:43:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5872kb
  • [2024-03-06 08:43:26]
  • 提交

answer

#include<bits/stdc++.h>

#define db double
#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 3e5 + 5;
const db eps = 1e-5, inf = 1e15;

int n, pos;
db a[N], s[N];

inline int check(db v) {
	db mx1 = -inf, mx2 = -inf;
	rep(i, 1, n) 
		if(i < pos) mx1 = max(mx1, s[i] - (pos - i) * v);
		else if(i > pos) mx2 = max(mx2, s[i] - (i - pos) * v);
	return mx1 + mx2 + a[pos] - v >= 0.0;
}

inline void testcase() {
	n = read(); 
	rep(i, 1, n) a[i] = read(), s[i] = 0;
	rep(i, 2, n) if(a[i] < a[i - 1] && a[i] < a[i + 1]) pos = i;
	rep(i, pos + 1, n) s[i] = s[i - 1] + a[i];
	lep(i, pos - 1, 1) s[i] = s[i + 1] + a[i];
	
	db l = 0, r = 1e9, mid;
	while(l + eps <= r) {
		mid = (l + r) / 2.0;
		if(check(mid)) l = mid;
		else r = mid;
	}
	printf("%.30lf\n", r);
}

signed main() {
	int t = read(); while(t--) testcase(); 
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5872kb

input:

2
4
8 2 7 10
6
9 6 5 3 4 8

output:

6.750006775746442144736647605896
5.833335592342336894944310188293

result:

wrong answer 1st numbers differ - expected: '6.7500000', found: '6.7500068', error = '0.0000010'