# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1060777 | 2024-08-15T22:33:48 Z | Alid | COVID tests (CEOI24_covid) | C++17 | 1706 ms | 14416 KB |
#include <vector> #include <queue> #include <math.h> #include <stdio.h> #include <algorithm> #include <string> using namespace std; bool test_pupils(vector<int>) ; const int NMAX = 1123; const int PMAX = 1123; int opt_ask[NMAX][PMAX]; double opt_val[NMAX][PMAX]; double powp[NMAX]; int permutate[NMAX]; void calc(int n, double p) { powp[0] = 1; for(int i=1;i<=n;i++) powp[i]=powp[i-1]*(1-p); opt_val[0][0] = 0; for(int len=1;len<=n;len++) { opt_val[len][1] = opt_val[len-1][0]; for(int prefix=2; prefix<=len; prefix++) { opt_val[len][prefix] = NMAX; for(int test_len=1;test_len<prefix;test_len++) { double pr = 1-powp[test_len]; pr /= 1-powp[prefix]; double v = 1 + pr * opt_val[len][test_len] + (1-pr) * opt_val[len-test_len][prefix-test_len]; if(v < opt_val[len][prefix]) { opt_ask[len][prefix] = test_len; opt_val[len][prefix] = v; } } } opt_val[len][0] = NMAX; for(int test_len=1;test_len<=len;test_len++) { double pr = 1-pow(1-p, test_len); double v = 1 + pr * opt_val[len][test_len] + (1-pr) * opt_val[len-test_len][0]; if(v < opt_val[len][0]) { opt_ask[len][0] = test_len; opt_val[len][0] = v; } } } fprintf(stderr, "Except: %lf\n", opt_val[n][0]); fprintf(stderr, "p = %lf\n", p); } bool calc_done; vector<int> test(int n, double p) { for(int i=0;i<n;i++) permutate[i]=i; srand(4); random_shuffle(permutate, permutate+n); if(!calc_done) calc(n,p); calc_done = true; vector<int> ans; for(int start = 0, prefix=0; start<n;) { int len = n - start; if(prefix == 1) { ans.push_back(permutate[start]); prefix = 0; start++; } else { vector<int> ask; int test_len = opt_ask[len][prefix]; for(int i=0;i<test_len;i++) ask.push_back(permutate[i+start]); if(test_pupils(ask)) { prefix = test_len; } else { if(prefix) prefix -= test_len; start += test_len; } } } return ans; } int n; bool test_pupils(vector<int> pupils) { string out(n, '0'); for(int it : pupils) out[it]='1'; printf("Q %s\n", out.c_str()); fflush(stdout); char in; scanf(" %c", &in); return in=='P'; } int main() { double p; int t; scanf("%d%lf%d", &n, &p, &t); for(int ti=0; ti<t; ti++) { auto positive = test(n, p); { string out(n, '0'); for(int it : positive) out[it]='1'; printf("A %s\n", out.c_str()); fflush(stdout); char in; scanf(" %c", &in); if(in != 'C') return 0; } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 283 ms | 14160 KB | Output is correct |
2 | Correct | 273 ms | 14244 KB | Output is correct |
3 | Correct | 284 ms | 14416 KB | Output is correct |
4 | Correct | 274 ms | 14216 KB | Output is correct |
5 | Correct | 278 ms | 13996 KB | Output is correct |
6 | Correct | 286 ms | 14160 KB | Output is correct |
7 | Correct | 284 ms | 14160 KB | Output is correct |
8 | Correct | 286 ms | 13988 KB | Output is correct |
9 | Correct | 273 ms | 14160 KB | Output is correct |
10 | Correct | 285 ms | 14200 KB | Output is correct |
11 | Correct | 276 ms | 14160 KB | Output is correct |
12 | Correct | 278 ms | 14212 KB | Output is correct |
13 | Correct | 276 ms | 14416 KB | Output is correct |
14 | Correct | 274 ms | 13984 KB | Output is correct |
15 | Correct | 282 ms | 14160 KB | Output is correct |
16 | Correct | 272 ms | 13988 KB | Output is correct |
17 | Correct | 265 ms | 13988 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 306 ms | 14240 KB | Output is correct (P=0.001, F=15.1, Q=10.8) -> 90.00 points |
2 | Correct | 385 ms | 14160 KB | Output is correct (P=0.005256, F=51.1, Q=46.3) -> 90.00 points |
3 | Correct | 468 ms | 13988 KB | Output is correct (P=0.011546, F=94.9, Q=90.4) -> 90.00 points |
4 | Correct | 645 ms | 14416 KB | Output is correct (P=0.028545, F=191.5, Q=187.6) -> 90.00 points |
5 | Correct | 726 ms | 14160 KB | Output is correct (P=0.039856, F=246.3, Q=243.6) -> 90.00 points |
6 | Correct | 958 ms | 14160 KB | Output is correct (P=0.068648, F=366.2, Q=364.4) -> 90.00 points |
7 | Correct | 1159 ms | 14160 KB | Output is correct (P=0.104571, F=490.3, Q=488.4) -> 90.00 points |
8 | Correct | 1516 ms | 14160 KB | Output is correct (P=0.158765, F=639.1, Q=632.9) -> 90.00 points |
9 | Correct | 1706 ms | 14160 KB | Output is correct (P=0.2, F=731.4, Q=729.8) -> 90.00 points |