QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131590#4676. Amalgamated ArtichokesPetroTarnavskyi#WA 3ms3876kbC++171.5kb2023-07-27 18:14:372023-07-27 18:14:41

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-27 18:14:41]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3876kb
  • [2023-07-27 18:14:37]
  • 提交

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;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int n;
	db p[4];
	cin >> n;
	FOR(i, 0, 4) {
		cin >> p[i];
	}
	vector<LL> fact(n + 1);
	vector<db> pw[4];
	FOR(i, 0, 4) {
		pw[i].resize(n + 1);
		pw[i][0] = 1;
		FOR(j, 1, n + 1) {
			pw[i][j] = pw[i][j - 1] * p[i];
		}
	}
	fact[0] = 1;
	FOR(i, 1, n + 1) {
		fact[i] = fact[i - 1] * i;
	}
	map<db, LL> mp;
	FOR(c0, 0, n + 1) {
		FOR(c1, 0, n + 1 - c0) {
			FOR(c2, 0, n + 1 - c0 - c1) {
				int c3 = n - c0 - c1 - c2;
				mp[pw[0][c0] * pw[1][c1] * pw[2][c2] * pw[3][c3]] += fact[n] / (fact[c0] * fact[c1] * fact[c2] * fact[c3]);
			}
		}
	}
	db ans = 0;
	while (!mp.empty()) {
		auto [val, cnt] = *mp.begin();
		mp.erase(mp.begin());
		if (cnt > 1) {
			mp[2 * val] += cnt / 2;
			ans += 2 * (cnt / 2) * val;
		}
		if (cnt % 2 == 1) {
			if (mp.empty()) {
				break;
			}
			auto [val2, cnt2] = *mp.begin();
			mp[val + val2]++;
			ans += val + val2;
			mp[val2]--;
		}
	}
	cout << ans << "\n";
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 3876kb

input:

42 1 23 4 8 10

output:

4497732589086637841696283158176189878794858701231472246784.0000000000

result:

wrong answer 1st numbers differ - expected: '104.8551105', found: '4497732589086637817876517473710497436358636181007697444864.0000000', error = '42894738927133330094387930054069818748442186131951321088.0000000'