QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414831#6565. Game Show Eliminationkaruna#Compile Error//C++204.1kb2024-05-19 20:30:262024-05-19 20:30:26

Judging History

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

  • [2024-05-19 20:30:26]
  • 评测
  • [2024-05-19 20:30:26]
  • 提交

answer

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int K = 10;
const int SZ = 1 << K;

int n, k;

double f(int x) {
	if (-k <= x && x <= 0) {
		return 1 - 0.5 * (1 + (double)x / k) * (1 + (double)x / k);
	}
	else if (x <= k) {
		return 0.5 * (1 - (double)x / k) * (1 - (double)x / k);
	}
	else {
		return 0.0;
	}
}

double pre[K][1 << K][K + 1], pre2[1 << K][K];
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> n >> k;

	for (int msk = 0; msk < (1 << (k - 1)); msk++) {
		pre2[msk][k - 1] = 1;
		for (int i = 0; i < k - 1; i++) {
			if (msk >> i & 1) {
				pre2[msk][k - 1] *= f(i + 1);
			}
		}

		for (int i = 0; i < k - 1; i++) {
			double prb = 1;
			if (~msk >> i & 1) {
				prb = 0;
			}

			for (int j = i + 1; j < k - 1; j++) {
				if (msk >> j & 1) {
					prb *= f(j - i);
				}
			}

			pre2[msk][i] = prb;
		}
	}

	
	for (int d = 1; d < k; d++) {
		for (int msk = 0; msk < (1 << (k - 1)); msk++) {

			vector<int> V;
			for (int i = 0; i < k - 1; i++) {
				if (msk >> i & 1) {
					V.push_back(xp - i - 1);
				}
			}
			V.push_back(xp);
			V.push_back(x);

			for (int i = 0; i < V.size(); i++) {
				double tot = 0;
				for (int j = 0; j < V.size(); j++) {
					double prb = 1 - f(V[i] - V[j]);
					for (int k = 0; k < V.size(); k++) {
						prb *= f(V[i] - V[k]);
					}
					tot += prb;
				}
				pre[d][msk][i] = tot;
			}
		}
	}

	queue<pair<pii, int>> Q;
	map<pair<pii, int>, double> dp;

	Q.push({{n, 1}, (1 << min(k - 1, n - 2)) - 1});
	dp[Q.front()] = 1;

	vector<double> ans(n + 2);

	auto upd = [&](int l, int r, double x) {
		ans[l] += x;
		ans[r + 1] -= x;
	};

	while (!Q.empty()) {
		auto [comp, msk] = Q.front();
		double prb = dp[Q.front()];
		Q.pop();

		auto [x, xp] = comp;
		if (xp != -1 && x - xp == k) {
			int cnt = max(xp - (k - 1) - 1, 0) + __builtin_popcount(msk) + 1;
			upd(x, x, prb * cnt);

			x = xp;
			xp = -1;
		}

		if (xp != -1) {
			if (xp - k >= 1) {
				upd(1, xp - k, prb);
			}

			for (int i = 0; i < k - 1; i++) [
				if (msk >> i & 1) {
					upd(xp - i - 1, xp - i - 1, prb);
				}
			]
			upd(xp, xp, prb);
			upd(x, x, prb);

			// dp[x][x - xp][msk]가 있고
			for (int i = 0; i < k - 1; i++) if (msk >> i & 1) {
				dp[{{x, xp}, msk ^ (1 << i)}] += prb * pre[x][msk][x - xp];
			}

			// x가 2등이야
			{
				int xpp = (msk) ? xp - 1 - __lg(msk & -msk) : xp - k;

				if (xpp <= 0) {
					upd(x, x, prb * pre[x][msk][k]);
					upd(xp, xp, prb * (1 + pre[x][msk][k]));
				}
				else {
					int nsk = msk >> (xp - xpp);
					nsk ^= (1 << k - 1) - (1 << (k - 1 - xp + xpp));
					nsk &= (1 << min(k - 1, xpp - 1)) - 1;

					dp[{{xp, xpp}, nsk}] += prb * pre[x][msk][k];
				}
			}

			// xp가 2등이야
			{
				int xpp = (msk) ? xp - 1 - __lg(msk & -msk) : xp - k;
				
				if (xpp <= 0) {
					upd(xp, xp, prb * pre[x][msk][k - 1]);
					upd(x, x, prb * (1 + pre[x][msk][k - 1]));
				}
				else {
					int nsk = msk >> (xp - xpp);
					nsk ^= (1 << k - 1) - (1 << (k - 1 - xp + xpp));
					nsk &= (1 << min(k - 1, xpp - 1)) - 1;

					dp[{{x, xpp}, nsk}] += prb * pre[x][msk][k - 1];
				}
			}
		}
		else {
			if (x - k > 0) {
				upd(1, x - k, prb);
			}
			upd(x, x, prb);
			for (int i = 0; i < k - 1; i++) {
				if (msk >> i & 1) {
					upd(x - i - 1, prb);
				}
			}
			// x가 1등이야

			{
				int xp = (msk) ? x - 1 - __lg(msk & -msk) : x - k;

				if (xp <= 0) {
					// nothing to do
				}
				else {
					int nsk = msk >> (x - xp);
					nsk ^= (1 << (k - 1)) - (1 << (k - 1 - x + xp));
					nsk &= (1 << min(k - 1, xp - 1)) - 1;

					dp[{{xp, -1}, nsk}] += prb * pre2[msk][k - 1];
				}
			}

			for (int i = 0; i < k - 1; i++) if (msk >> i & 1) {
				dp[{{x, -1}, msk ^ (1 << i)}] += prb * pre2[msk][i];
			}
		}
	}

	cout.precision(10);
	for (int i = 1; i <= n; i++) {
		ans[i] += ans[i - 1];

		cout << fixed << n - ans[i] << '\n';
	}
}

Details

answer.code: In function ‘int main()’:
answer.code:64:53: error: ‘xp’ was not declared in this scope; did you mean ‘exp’?
   64 |                                         V.push_back(xp - i - 1);
      |                                                     ^~
      |                                                     exp
answer.code:67:37: error: ‘xp’ was not declared in this scope; did you mean ‘exp’?
   67 |                         V.push_back(xp);
      |                                     ^~
      |                                     exp
answer.code:68:37: error: ‘x’ was not declared in this scope
   68 |                         V.push_back(x);
      |                                     ^
answer.code:117:33: error: expected identifier before ‘if’
  117 |                                 if (msk >> i & 1) {
      |                                 ^~
answer.code: In lambda function:
answer.code:121:25: error: expected ‘{’ before ‘upd’
  121 |                         upd(xp, xp, prb);
      |                         ^~~
answer.code: In function ‘int main()’:
answer.code:120:26: error: expected ‘;’ before ‘upd’
  120 |                         ]
      |                          ^
      |                          ;
  121 |                         upd(xp, xp, prb);
      |                         ~~~
answer.code:170:44: error: no match for call to ‘(main()::<lambda(int, int, double)>) (std::tuple_element<0, std::pair<int, int> >::type, double&)’
  170 |                                         upd(x - i - 1, prb);
      |                                         ~~~^~~~~~~~~~~~~~~~
answer.code:92:20: note: candidate: ‘main()::<lambda(int, int, double)>’
   92 |         auto upd = [&](int l, int r, double x) {
      |                    ^
answer.code:92:20: note:   candidate expects 3 arguments, 2 provided