Submission #528054
Source Code Expand
/*{{{*/ #include <cassert> #include <cctype> #include <climits> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <bitset> #include <deque> #include <list> #include <map> #include <queue> #include <set> #include <tuple> #include <unordered_map> #include <unordered_set> #include <vector> #include <iostream> #include <string> #include <sstream> using namespace std; typedef int8_t sbyte; typedef uint8_t byte; typedef uint16_t ushort; typedef uint32_t uint; typedef int64_t i64; typedef uint64_t u64; template<class T> static inline T ABS(T x) {return x < 0 ? -x : x;} template<class T> static inline void MAZ(T &a, const T &b) {if(a < b) a = b;} template<class T> static inline void MIZ(T &a, const T &b) {if(b < a) a = b;} /*}}}*/ static int S[81][4]; static int N[3]; static int P[3], Q[3]; static int R[3]; static double DP[101 * 101 * 101]; static inline int myhash(const int *r) { return r[0] * 101 * 101 + r[1] * 101 + r[2]; } static void solve() { auto hR = myhash(R); if(hR == 0) return; auto ret = 1e100; for(auto s = 0; s < 81; s++) { if(R[S[s][0]] == 0) continue; auto ta = 0., tb = 1.; auto p = 1, q = 1; int r[3] = {R[0], R[1], R[2]}; auto hr = hR; for(auto i = 0; i < 4; i++) { auto lvl = S[s][i]; if(r[lvl] == 0) { tb += DP[hr] * p / q; break; } if(Q[lvl] != 0) { if(hr != hR) { tb += DP[hr] * (p * Q[lvl]) / (q * 100); } else { ta += p * Q[lvl] / (double)(q * 100); } } r[lvl]--; hr = myhash(r); p *= P[lvl]; q *= 100; if(i == 2 && lvl == 0 || i == 3) { tb += DP[hr] * p / q; break; } } MIZ(ret, tb / (1 - ta)); } DP[hR] = ret; } static void solve_dfs(int dep) { if(dep == 3) { solve(); } else { for(auto n = 0; n <= N[dep]; n++) { R[dep] = n; solve_dfs(dep + 1); } } } static void build() { for(auto s = 0; s < 81; s++) { auto t = s; for(auto i = 4; --i >= 0; ) { S[s][i] = t % 3; t /= 3; } } } int main() { build(); for(auto i = 0; i < 3; i++) scanf("%d", N + i); for(auto i = 0; i < 3; i++) { scanf("%d", P + i); Q[i] = 100 - P[i]; } solve_dfs(0); printf("%.15f\n", DP[myhash(N)]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Game |
User | arosusti |
Language | C++11 (GCC 4.8.1) |
Score | 0 |
Code Size | 2361 Byte |
Status | TLE |
Exec Time | 2038 ms |
Memory | 8492 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:107:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for(auto i = 0; i < 3; i++) scanf("%d", N + i); ^ ./Main.cpp:109:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", P + i); ^
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask0_sample_05.txt |
All | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask0_sample_05.txt, subtask1_manual_01.txt, subtask1_manual_02.txt, subtask1_manual_03.txt, subtask1_manual_04.txt, subtask1_manual_05.txt, subtask1_manual_06.txt, subtask1_manual_07.txt, subtask1_random_01.txt, subtask1_random_02.txt, subtask1_random_03.txt, subtask1_random_04.txt, subtask1_random_05.txt, subtask1_random_06.txt, subtask1_random_07.txt, subtask1_random_08.txt, subtask1_random_09.txt, subtask1_random_10.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 27 ms | 976 KB |
subtask0_sample_02.txt | TLE | 2037 ms | 7716 KB |
subtask0_sample_03.txt | AC | 26 ms | 1044 KB |
subtask0_sample_04.txt | AC | 27 ms | 1040 KB |
subtask0_sample_05.txt | AC | 47 ms | 1196 KB |
subtask1_manual_01.txt | AC | 27 ms | 1040 KB |
subtask1_manual_02.txt | AC | 28 ms | 1044 KB |
subtask1_manual_03.txt | AC | 26 ms | 1036 KB |
subtask1_manual_04.txt | TLE | 2034 ms | 3240 KB |
subtask1_manual_05.txt | TLE | 2037 ms | 3244 KB |
subtask1_manual_06.txt | TLE | 2038 ms | 8492 KB |
subtask1_manual_07.txt | TLE | 2037 ms | 4140 KB |
subtask1_random_01.txt | AC | 1379 ms | 6508 KB |
subtask1_random_02.txt | AC | 532 ms | 2220 KB |
subtask1_random_03.txt | AC | 401 ms | 3500 KB |
subtask1_random_04.txt | AC | 150 ms | 1120 KB |
subtask1_random_05.txt | AC | 792 ms | 2352 KB |
subtask1_random_06.txt | AC | 1350 ms | 6088 KB |
subtask1_random_07.txt | AC | 499 ms | 2604 KB |
subtask1_random_08.txt | AC | 901 ms | 2400 KB |
subtask1_random_09.txt | AC | 611 ms | 2600 KB |
subtask1_random_10.txt | AC | 521 ms | 2156 KB |