Submission #1037099

#TimeUsernameProblemLanguageResultExecution timeMemory
1037099RaimondCounting Mushrooms (IOI20_mushrooms)C++17
61.58 / 100
7 ms600 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; #define N '\n'; #define VI <vector <int>> #define VVI <vector <vector <int>>> int count_mushrooms(int n){ int cnt = 1; if(n <= 226){ for(int i = 1; i < n; i++){ cnt += 1 - use_machine({0, i}); } return cnt; } vector <int> As = {0}; vector <int> Bs; int mn = 10000, ans; for(int i = 1; i < 500; i++){ if(2*i + ((n - (2*i)) / i) < mn){ mn = 2*i + ((n - (2*i)) / i); ans = i; } } int unt = ans*2; // 188 - 1 = 187 for(int i = 1; i < unt; i++){ bool q = use_machine({0,i}); if(q) Bs.push_back(i); else As.push_back(i); } cnt += As.size()-1; int i = unt; // n - 188 / 94 for(; i < n;){ if(As.size() >= Bs.size()){ vector<int> search; vector <int> Is; int j = 0; for(; j < As.size() && i < n; j++ ){ search.push_back(i); Is.push_back(i); search.push_back(As[j]); i++; } int q = use_machine(search); cnt += (search.size()/2) - ((q/2) +(q % 2)); if(q/2 + q % 2 == 0){ for(int ii = 0; ii < Is.size(); ii++){ As.push_back(Is[ii]); } } if(q % 2 != 0){ Bs.push_back(Is[0]); } } else{ vector<int> search; vector <int> Is; for(int j = 0; j < Bs.size() && i < n; j++){ search.push_back(i); Is.push_back(i); search.push_back(Bs[j]); i++; } int q = use_machine(search); cnt += q/2 + q % 2; if(q/2 + q % 2 == 0 ){ for(int ii = 0; ii < Is.size(); ii++){ Bs.push_back(Is[ii]); } } if(q % 2 != 0){ As.push_back(Is[0]); } } } // B A B A B A // B A A A B A B A return cnt; }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for(; j < As.size() && i < n; j++ ){
      |                   ~~^~~~~~~~~~~
mushrooms.cpp:57:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 for(int ii = 0; ii < Is.size(); ii++){
      |                                 ~~~^~~~~~~~~~~
mushrooms.cpp:68:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int j = 0; j < Bs.size() && i < n; j++){
      |                            ~~^~~~~~~~~~~
mushrooms.cpp:78:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 for(int ii = 0; ii < Is.size(); ii++){
      |                                 ~~~^~~~~~~~~~~
mushrooms.cpp:30:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     int unt = ans*2;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...