Submission #1070494

#TimeUsernameProblemLanguageResultExecution timeMemory
1070494andrei_iorgulescuCounting Mushrooms (IOI20_mushrooms)C++14
88.63 / 100
7 ms600 KiB
#include <bits/stdc++.h> #include "mushrooms.h" #warning That's not FB, that's my FB using namespace std; int count_mushrooms(int n) { srand(2082); vector<int> A, B; A.push_back(0); if (n <= 227) { int ans = 1; for (int i = 1; i < n; i++) ans += 1 - use_machine({0,i}); return ans; } for (int i = 1; i <= 10; i++) { vector<int> idd; for (int j = 0; j < min(n, 500); j++) idd.push_back(j); shuffle(idd.begin(), idd.end(), default_random_engine(rand())); int xxx = use_machine(idd); } int hh = use_machine({0,1}); if (hh == 0) A.push_back(1); else B.push_back(1); if (hh == 1) { int hhh = use_machine({0,2}); if (hhh == 0) A.push_back(2); else B.push_back(2); } int a = A.size(), b = B.size(); ///caut cel mai bun max(a,b) la care sa ma opresc din spamat int best, omin = 1e9; for (int i = 5; i <= 1000 and 2 * i <= n; i++) { int cur = i - 1; int cate = n - 2 * i - 1; int j = -1; while (cate > 0) { j++; cur++; cate -= (i + j / 2); } if (cur < omin) { omin = cur; best = i; } } best--; vector<int> unsolved; if (hh == 1) { for (int i = 3; i < n; i++) unsolved.push_back(i); } else { for (int i = 2; i < n; i++) unsolved.push_back(i); } reverse(unsolved.begin(),unsolved.end()); while (max(a,b) < best) { if (a >= 2) { vector<int> mac = {unsolved[unsolved.size() - 1], A[0], unsolved[unsolved.size() - 2], A[1]}; int xxx = use_machine(mac); if (xxx == 0) { A.push_back(unsolved.back()); unsolved.pop_back(); A.push_back(unsolved.back()); unsolved.pop_back(); } else if (xxx == 1) { B.push_back(unsolved.back()); unsolved.pop_back(); A.push_back(unsolved.back()); unsolved.pop_back(); } else if (xxx == 2) { A.push_back(unsolved.back()); unsolved.pop_back(); B.push_back(unsolved.back()); unsolved.pop_back(); } else { B.push_back(unsolved.back()); unsolved.pop_back(); B.push_back(unsolved.back()); unsolved.pop_back(); } } else { vector<int> mac = {unsolved[unsolved.size() - 1], B[0], unsolved[unsolved.size() - 2], B[1]}; int xxx = use_machine(mac); if (xxx == 0) { B.push_back(unsolved.back()); unsolved.pop_back(); B.push_back(unsolved.back()); unsolved.pop_back(); } else if (xxx == 1) { A.push_back(unsolved.back()); unsolved.pop_back(); B.push_back(unsolved.back()); unsolved.pop_back(); } else if (xxx == 2) { B.push_back(unsolved.back()); unsolved.pop_back(); A.push_back(unsolved.back()); unsolved.pop_back(); } else { A.push_back(unsolved.back()); unsolved.pop_back(); A.push_back(unsolved.back()); unsolved.pop_back(); } } a = A.size(); b = B.size(); } int ans = A.size(); while (!unsolved.empty()) { int k = max(a,b); vector<int> cr; for (int i = 0; i < k; i++) { if (!unsolved.empty()) { cr.push_back(unsolved.back()); unsolved.pop_back(); } } if (a >= b) { vector<int> tq; for (int i = 0; i < cr.size(); i++) { tq.push_back(cr[i]); tq.push_back(A[i]); } int xxx = use_machine(tq); if (xxx % 2 == 1) B.push_back(cr[0]), xxx--; else A.push_back(cr[0]), ans++; ans += (2 * ((int)cr.size() - 1) - xxx) / 2; } else { vector<int> tq; for (int i = 0; i < cr.size(); i++) { tq.push_back(cr[i]); tq.push_back(B[i]); } int xxx = use_machine(tq); if (xxx % 2 == 1) A.push_back(cr[0]), ans++, xxx--; else B.push_back(cr[0]); ans += xxx / 2; } a = A.size(); b = B.size(); } return ans; } /** Aflu sa zicem doua A-uri, dau spamez AxAy ca unic determina x si y, candva ma opresc Sa zicem ca am a A-uri si b B-uri While (mai am nedescoperite) { k = max(a,b); Bag x1Ax2A...xkA, astfel aflu cate din x sunt A-uri dar aflu si exact cum e x1, il bag in A-uri sau B-uri si dau a++ sau b++ } Fara ultima optimizare era fix 2sqrt, asa idk, doamne ajuta **/

Compilation message (stderr)

mushrooms.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:25:13: warning: unused variable 'xxx' [-Wunused-variable]
   25 |         int xxx = use_machine(idd);
      |             ^~~
mushrooms.cpp:160:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |             for (int i = 0; i < cr.size(); i++)
      |                             ~~^~~~~~~~~~~
mushrooms.cpp:175:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |             for (int i = 0; i < cr.size(); i++)
      |                             ~~^~~~~~~~~~~
mushrooms.cpp:60:9: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     best--;
      |     ~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...