# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
827317 | 2023-08-16T10:54:06 Z | Amylopectin | Counting Mushrooms (IOI20_mushrooms) | C++14 | 452 ms | 584 KB |
#include "mushrooms.h" #include <stdio.h> #include <iostream> #include <vector> #include <stdlib.h> #include <time.h> using namespace std; const int mxn = 1e5 + 10,bo = 82; int ta[2][mxn] = {},nu[mxn] = {},u[mxn] = {}; vector<int> fa; int count_mushrooms(int n) { int i,j,cn,cm,fn,fm,co[2] = {1,0},cru = 1,cou,cva,us,ans = 0,fi; srand(time(0)); ta[0][0] = 0; u[0] = 1; nu[0] = 0; for(i=1; i<n; i++) { cn = rand() % (n-i); cou = 0; for(j=0; j<n; j++) { if(u[j] == 0) { if(cou == cn) { nu[i] = j; u[j] = 1; break; } else { cou ++; } } } } if(n == 1) { return 1; } if(n - cru == 1) { fa.clear(); fa.push_back(nu[cru]); fa.push_back(0); cva = use_machine(fa); if(cva == 0) { ta[0][co[0]] = nu[cru]; co[0] ++; } else { ta[1][co[1]] = nu[cru]; co[1] ++; } cru ++; return co[0]; } fa.clear(); fa.push_back(nu[cru]); fa.push_back(0); fa.push_back(nu[cru+1]); cva = use_machine(fa); if(cva == 0) { ta[0][co[0]] = nu[cru]; ta[0][co[0] + 1] = nu[cru + 1]; co[0] += 2; } else if(cva == 2) { ta[1][co[1]] = nu[cru]; ta[1][co[1] + 1] = nu[cru + 1]; co[1] += 2; } else { fa.pop_back(); cva = use_machine(fa); if(cva == 0) { ta[0][co[0]] = nu[cru]; ta[1][co[1]] = nu[cru+1]; co[0] ++; co[1] ++; } else { ta[0][co[0]] = nu[cru+1]; ta[1][co[1]] = nu[cru]; co[0] ++; co[1] ++; } } cru += 2; // for(i=0; i<n; i++) // { // printf("%d ",nu[i]); // } while(cru < n) { if(n - cru == 1) { fa.clear(); fa.push_back(nu[cru]); fa.push_back(0); cva = use_machine(fa); if(cva == 0) { ta[0][co[0]] = nu[cru]; co[0] ++; } else { ta[1][co[1]] = nu[cru]; co[1] ++; } cru ++; break; } if(co[0] >= 2) { fa.clear(); fa.push_back(nu[cru]); fa.push_back(ta[0][0]); fa.push_back(nu[cru+1]); fa.push_back(ta[0][1]); cva = use_machine(fa); if(cva == 0) { ta[0][co[0]] = nu[cru]; ta[0][co[0] + 1] = nu[cru + 1]; co[0] += 2; } else if(cva == 1) { ta[0][co[0]] = nu[cru+1]; ta[1][co[1]] = nu[cru]; co[0] ++; co[1] ++; } else if(cva == 2) { ta[0][co[0]] = nu[cru]; ta[1][co[1]] = nu[cru+1]; co[0] ++; co[1] ++; } else { ta[1][co[1]] = nu[cru]; ta[1][co[1] + 1] = nu[cru + 1]; co[1] += 2; } } else { fa.clear(); fa.push_back(nu[cru]); fa.push_back(ta[1][0]); fa.push_back(nu[cru+1]); fa.push_back(ta[1][1]); cva = use_machine(fa); if(cva == 0) { ta[1][co[1]] = nu[cru]; ta[1][co[1] + 1] = nu[cru + 1]; co[1] += 2; } else if(cva == 1) { ta[0][co[0]] = nu[cru]; ta[1][co[1]] = nu[cru+1]; co[0] ++; co[1] ++; } else if(cva == 2) { ta[0][co[0]] = nu[cru+1]; ta[1][co[1]] = nu[cru]; co[0] ++; co[1] ++; } else { ta[0][co[0]] = nu[cru]; ta[0][co[0] + 1] = nu[cru + 1]; co[0] += 2; } } // fa.clear(); // fa.push_back(nu[cru]); // fa.push_back(0); // fa.push_back(nu[cru+1]); // cva = use_machine(fa); // if(cva == 0) // { // ta[0][co[0]] = nu[cru]; // ta[0][co[0] + 1] = nu[cru + 1]; // co[0] += 2; // } // else if(cva == 2) // { // ta[1][co[1]] = nu[cru]; // ta[1][co[1] + 1] = nu[cru + 1]; // co[1] += 2; // } // else // { // fa.pop_back(); // cva = use_machine(fa); // if(cva == 0) // { // ta[0][co[0]] = nu[cru]; // ta[1][co[1]] = nu[cru+1]; // co[0] ++; // co[1] ++; // } // else // { // ta[0][co[0]] = nu[cru+1]; // ta[1][co[1]] = nu[cru]; // co[0] ++; // co[1] ++; // } // } cru += 2; if(co[0] >= bo || co[1] >= bo) { if(co[0] >= bo) { us = 0; } else { us = 1; } break; } } ans = co[0]; while(cru < n) { fa.clear(); cou = 0; if(co[0] > co[1]) { us = 0; } else { us = 1; } for(i=0; i<co[us]; i++) { if(cru < n) { cou ++; if(i == 0) { fi = nu[cru]; } fa.push_back(nu[cru]); cru ++; } fa.push_back(ta[us][i]); } cva = use_machine(fa); if(us == 0) { if(cva % 2 == 0) { ans ++; ta[0][co[0]] = fi; co[0] ++; } else { ta[1][co[1]] = fi; co[1] ++; } ans += cou - 1 - (cva/2); } else { if(cva % 2 == 1) { ans ++; ta[0][co[0]] = fi; co[0] ++; } else { ta[1][co[1]] = fi; co[1] ++; } ans += cva/2; } } return ans; // std::vector<int> m; // for (int i = 0; i < n; i++) // m.push_back(i); // int c1 = use_machine(m); // m = {0, 1}; // int c2 = use_machine(m); // return c1+c2; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 208 KB | Output is correct |
2 | Correct | 0 ms | 208 KB | Output is correct |
3 | Correct | 0 ms | 208 KB | Output is correct |
4 | Correct | 0 ms | 208 KB | Output is correct |
5 | Correct | 1 ms | 208 KB | Output is correct |
6 | Correct | 4 ms | 336 KB | Output is correct |
7 | Correct | 432 ms | 472 KB | Output is correct |
8 | Correct | 425 ms | 584 KB | Output is correct |
9 | Correct | 421 ms | 436 KB | Output is correct |
10 | Correct | 414 ms | 512 KB | Output is correct |
11 | Partially correct | 421 ms | 544 KB | Output is partially correct |
12 | Correct | 409 ms | 388 KB | Output is correct |
13 | Correct | 418 ms | 560 KB | Output is correct |
14 | Correct | 95 ms | 360 KB | Output is correct |
15 | Partially correct | 413 ms | 396 KB | Output is partially correct |
16 | Partially correct | 419 ms | 536 KB | Output is partially correct |
17 | Correct | 86 ms | 348 KB | Output is correct |
18 | Correct | 412 ms | 392 KB | Output is correct |
19 | Partially correct | 433 ms | 420 KB | Output is partially correct |
20 | Correct | 421 ms | 532 KB | Output is correct |
21 | Correct | 415 ms | 476 KB | Output is correct |
22 | Partially correct | 427 ms | 456 KB | Output is partially correct |
23 | Correct | 413 ms | 420 KB | Output is correct |
24 | Correct | 83 ms | 360 KB | Output is correct |
25 | Partially correct | 418 ms | 384 KB | Output is partially correct |
26 | Partially correct | 418 ms | 568 KB | Output is partially correct |
27 | Partially correct | 415 ms | 416 KB | Output is partially correct |
28 | Partially correct | 414 ms | 396 KB | Output is partially correct |
29 | Partially correct | 416 ms | 440 KB | Output is partially correct |
30 | Partially correct | 418 ms | 452 KB | Output is partially correct |
31 | Partially correct | 413 ms | 440 KB | Output is partially correct |
32 | Partially correct | 419 ms | 536 KB | Output is partially correct |
33 | Partially correct | 419 ms | 412 KB | Output is partially correct |
34 | Partially correct | 419 ms | 432 KB | Output is partially correct |
35 | Partially correct | 420 ms | 384 KB | Output is partially correct |
36 | Partially correct | 422 ms | 436 KB | Output is partially correct |
37 | Partially correct | 417 ms | 412 KB | Output is partially correct |
38 | Partially correct | 420 ms | 440 KB | Output is partially correct |
39 | Partially correct | 418 ms | 448 KB | Output is partially correct |
40 | Partially correct | 421 ms | 392 KB | Output is partially correct |
41 | Partially correct | 420 ms | 464 KB | Output is partially correct |
42 | Partially correct | 421 ms | 472 KB | Output is partially correct |
43 | Partially correct | 429 ms | 404 KB | Output is partially correct |
44 | Partially correct | 423 ms | 396 KB | Output is partially correct |
45 | Partially correct | 420 ms | 540 KB | Output is partially correct |
46 | Partially correct | 452 ms | 508 KB | Output is partially correct |
47 | Partially correct | 418 ms | 448 KB | Output is partially correct |
48 | Partially correct | 445 ms | 568 KB | Output is partially correct |
49 | Partially correct | 416 ms | 456 KB | Output is partially correct |
50 | Partially correct | 419 ms | 520 KB | Output is partially correct |
51 | Partially correct | 417 ms | 380 KB | Output is partially correct |
52 | Partially correct | 426 ms | 396 KB | Output is partially correct |
53 | Partially correct | 414 ms | 476 KB | Output is partially correct |
54 | Partially correct | 424 ms | 436 KB | Output is partially correct |
55 | Partially correct | 428 ms | 396 KB | Output is partially correct |
56 | Partially correct | 418 ms | 456 KB | Output is partially correct |
57 | Partially correct | 422 ms | 516 KB | Output is partially correct |
58 | Partially correct | 417 ms | 456 KB | Output is partially correct |
59 | Partially correct | 416 ms | 516 KB | Output is partially correct |
60 | Partially correct | 420 ms | 384 KB | Output is partially correct |
61 | Partially correct | 446 ms | 456 KB | Output is partially correct |
62 | Correct | 1 ms | 208 KB | Output is correct |
63 | Correct | 0 ms | 316 KB | Output is correct |
64 | Correct | 0 ms | 208 KB | Output is correct |
65 | Correct | 0 ms | 208 KB | Output is correct |
66 | Correct | 0 ms | 208 KB | Output is correct |
67 | Correct | 0 ms | 208 KB | Output is correct |
68 | Correct | 0 ms | 208 KB | Output is correct |
69 | Correct | 0 ms | 208 KB | Output is correct |
70 | Correct | 0 ms | 208 KB | Output is correct |
71 | Correct | 0 ms | 208 KB | Output is correct |
72 | Correct | 0 ms | 208 KB | Output is correct |
73 | Correct | 0 ms | 208 KB | Output is correct |
74 | Correct | 0 ms | 208 KB | Output is correct |
75 | Correct | 0 ms | 208 KB | Output is correct |
76 | Correct | 0 ms | 208 KB | Output is correct |
77 | Correct | 0 ms | 208 KB | Output is correct |
78 | Correct | 0 ms | 208 KB | Output is correct |
79 | Correct | 0 ms | 208 KB | Output is correct |
80 | Correct | 0 ms | 208 KB | Output is correct |
81 | Correct | 0 ms | 208 KB | Output is correct |
82 | Correct | 0 ms | 208 KB | Output is correct |
83 | Correct | 0 ms | 320 KB | Output is correct |
84 | Correct | 0 ms | 208 KB | Output is correct |
85 | Correct | 0 ms | 208 KB | Output is correct |
86 | Correct | 0 ms | 208 KB | Output is correct |
87 | Correct | 0 ms | 208 KB | Output is correct |
88 | Correct | 0 ms | 320 KB | Output is correct |
89 | Correct | 1 ms | 208 KB | Output is correct |
90 | Correct | 0 ms | 208 KB | Output is correct |
91 | Correct | 0 ms | 208 KB | Output is correct |