QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131871#5125. Adjusted AveragePetroTarnavskyi#WA 313ms3848kbC++171.8kb2023-07-28 17:28:452023-07-28 17:28:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-28 17:28:47]
  • 评测
  • 测评结果:WA
  • 用时:313ms
  • 内存:3848kb
  • [2023-07-28 17:28:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

typedef long double db;

long double solve(int n, int k, int x, vector<LL> a){
	LL sum = 0;
	FOR(i, 0, n){
		a[i] -= x;
		sum += a[i];
	}
	
	if(sum < 0){
		FOR(i, 0, n)
			a[i] *= -1;
		sum *= -1;
	}
	
	sort(ALL(a));
	LL mn = sum;
	if(k == 0)
		mn = sum;
	if(k == 1){
		FOR(i, 0, n)
			mn = min(mn, abs(sum - a[i]));
	}
	if(k == 2){
		FOR(i, 0, n)
			FOR(j, i + 1, n)
				mn = min(mn, abs(sum - a[i] - a[j]));
	}
	if(k == 3){
		FOR(i, 0, n)
			FOR(j, i + 1, n)
				FOR(z, j + 1, n)
					mn = min(mn, abs(sum - a[i] - a[j] - a[z]));
	}
	if(k == 4){
		FOR(i, 0, n - 3)
			FOR(j, i + 1, n - 2){
				int z = j + 1;
				
				LL cur = a[i] + a[j] + a[z];
				
				int pos = n - 1;
				
				while(z < n){
					
					while(pos > z && a[pos] + cur > sum)
						pos--;
					
					if(pos + 1 != n)		
						mn = min(mn, a[pos + 1] + cur - sum);
					
					if(pos == z)
						break;
					
					mn = min(mn, sum - a[pos] - cur);				
					z++;
				}
			}
	}
	
	
	
	
	return 1.0 * mn / (n - k);
} 




int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k, x;
	cin >> n >> k >> x;
	
	vector<LL> a(n);
	FOR(i, 0, n)
		cin >> a[i];

	db ans = solve(n, 0, x, a);
	FOR(i, 1, k + 1)
		ans = min(ans, solve(n, i, x, a));
		
	cout << fixed << setprecision(10) << ans << endl;

	
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3828kb

input:

5 2 2
1 2 3 100 200

output:

0.0000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

5 4 -5
-6 -3 0 6 3

output:

0.5000000000

result:

ok found '0.50000', expected '0.50000', error '0.00000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

4 1 4
1 3 3 7

output:

0.3333333333

result:

ok found '0.33333', expected '0.33333', error '0.00000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

2 1 0
0 0

output:

0.0000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

2 1 1
2 3

output:

1.0000000000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

4 1 0
-2 -1 1 2

output:

0.0000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

5 2 0
-1 2 3 -4 42

output:

0.0000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

6 2 0
-5 -1 1 3 3 5

output:

0.0000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

5 4 -1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

output:

2000000000.0000000000

result:

ok found '2000000000.00000', expected '2000000000.00000', error '0.00000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

5 4 1000000000
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000

output:

2000000000.0000000000

result:

ok found '2000000000.00000', expected '2000000000.00000', error '0.00000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

5 1 0
-16 -12 4 12 20

output:

1.0000000000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

8 2 0
-18 -6 -6 0 0 24 36 42

output:

1.0000000000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

5 1 0
10000 -10 -100 -1000 -3900

output:

998.0000000000

result:

ok found '998.00000', expected '998.00000', error '0.00000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

15 3 1
-3 3 0 -3 3 2 0 3 -1 -1 0 -3 1 -1 -2

output:

0.4166666667

result:

ok found '0.41667', expected '0.41667', error '0.00000'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

6 1 0
-1 -1 -1 1 1 1

output:

0.0000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

8 1 80
-90 52 -98 -79 70 86 38 -77

output:

80.0000000000

result:

ok found '80.00000', expected '80.00000', error '0.00000'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

5 3 37
3 72 88 23 -51

output:

0.5000000000

result:

ok found '0.50000', expected '0.50000', error '0.00000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

8 3 -50
-68 -98 34 55 -9 83 -64 -45

output:

1.8000000000

result:

ok found '1.80000', expected '1.80000', error '0.00000'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

5 2 62
-21 82 9 65 94

output:

0.3333333333

result:

ok found '0.33333', expected '0.33333', error '0.00000'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

10 4 -16
57 60 25 -60 -31 -70 25 -45 -8 -93

output:

0.0000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #21:

score: 0
Accepted
time: 313ms
memory: 3848kb

input:

1000 4 -589682264
239898913 202060748 -888127376 -880309095 124799170 -494539478 -745680608 726341697 992941811 -992809843 -977069412 -627162219 -243367314 325137914 647494705 994977955 32926705 618107495 702088915 19011397 546487463 811676912 -599600278 178857199 475002521 -328010873 568834738 -650...

output:

597654934.9678714275

result:

ok found '597654934.96787', expected '597654934.96787', error '0.00000'

Test #22:

score: 0
Accepted
time: 311ms
memory: 3844kb

input:

1000 4 -520031192
-828928297 -939974056 -890063527 -821483207 202331771 452507962 -984471175 730065137 -788464067 -814085288 -308486435 -251817293 982579015 -779352535 417038541 664276772 822475842 509497915 -536596860 616913996 358016799 -839048180 358771449 -538531644 562815966 635875550 337992251...

output:

558582928.1375502348

result:

ok found '558582928.13755', expected '558582928.13755', error '0.00000'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

5 3 78
-68 42 -52 42 50

output:

32.0000000000

result:

ok found '32.00000', expected '32.00000', error '0.00000'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

5 4 0
11 7 -13 -3 -6

output:

0.2500000000

result:

ok found '0.25000', expected '0.25000', error '0.00000'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

6 4 50483269
-812901056 614642221 945836657 -616198107 598529790 -614398526

output:

15984531.5000000000

result:

ok found '15984531.50000', expected '15984531.50000', error '0.00000'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

5 4 4
8 20 -18 3 9

output:

0.3333333333

result:

ok found '0.33333', expected '0.33333', error '0.00000'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

10 4 -472189650
-763683851 291512773 236754835 367611187 -650471393 -435169974 -783816043 -891608557 997972439 910540713

output:

36488132.5000000000

result:

ok found '36488132.50000', expected '36488132.50000', error '0.00000'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

6 4 -286216652
-146841360 -702906210 328658776 -159898481 154871206 -736124545

output:

2794288.0000000000

result:

ok found '2794288.00000', expected '2794288.00000', error '0.00000'

Test #29:

score: 0
Accepted
time: 209ms
memory: 3616kb

input:

1500 3 1
-3 -1 3 -1 1 -3 0 -2 -2 1 0 0 2 1 2 0 -2 -3 0 3 3 1 -2 0 1 2 0 0 -1 3 1 2 -1 0 -3 0 0 -2 -1 -3 2 3 0 0 3 -3 -3 -3 0 -3 0 2 -2 -2 3 -1 2 3 1 -2 -1 -2 -1 0 0 -2 2 2 2 -2 2 -1 3 -2 2 -3 -3 2 -2 3 -2 -1 2 -1 1 1 0 0 3 -3 3 -2 -2 -3 3 0 0 -3 2 -1 -2 1 2 0 0 3 0 1 3 2 -1 3 -1 1 -3 1 -2 1 -1 3 2 0...

output:

0.9719438878

result:

ok found '0.97194', expected '0.97194', error '0.00000'

Test #30:

score: 0
Accepted
time: 311ms
memory: 3764kb

input:

1000 4 0
-5 3 4 4 2 -2 -1 -3 -4 -1 2 -2 1 -3 4 0 -1 -5 -2 2 2 4 -2 -1 -2 -1 -2 -4 1 -1 3 -4 2 -1 -3 2 5 2 -1 -1 -1 -2 5 -5 0 -1 -4 3 5 0 3 2 -4 5 -3 -2 5 -1 -1 -3 -3 2 2 3 -3 1 5 2 -4 4 1 5 -5 -4 5 -2 -4 2 -4 1 0 -5 1 -4 1 1 -2 -4 5 4 -2 -4 1 -4 -5 3 -1 5 -4 -4 -5 -1 -2 -2 -1 -2 -5 2 5 3 -4 -1 1 3 5...

output:

0.0090361446

result:

ok found '0.00904', expected '0.00904', error '0.00000'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

10 4 -652315249
248814082 -310330977 -7639307 -808957195 -937992709 -461255220 526406959 317472565 958347317 -387890815

output:

166637545.1666666567

result:

ok found '166637545.16667', expected '166637545.16667', error '0.00000'

Test #32:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

6 4 802938834
279940040 -341612005 -603412852 781046065 -36716272 116954057

output:

272445781.5000000000

result:

ok found '272445781.50000', expected '272445781.50000', error '0.00000'

Test #33:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

20 4 221873446
849467103 884117952 312351432 -736878277 -296631326 -653303218 924111525 705904846 927004812 -810297249 860376579 744928549 -85282366 -877593960 698190037 840265628 -392839463 828364237 -422208014 198779260

output:

17181.1666666667

result:

ok found '17181.16667', expected '17181.16667', error '0.00000'

Test #34:

score: -100
Wrong Answer
time: 1ms
memory: 3648kb

input:

15 4 275628638
-847206183 782559411 141146580 425437384 810109824 -265811904 668678866 900016918 -401762002 358260741 574537650 -352457220 -504612680 418460859 909853096

output:

354545.3333333333

result:

wrong answer 1st numbers differ - expected: '125105.00000', found: '354545.33333', error = '1.83398'