Submission #1115022

#TimeUsernameProblemLanguageResultExecution timeMemory
1115022mightyrockCounting Mushrooms (IOI20_mushrooms)C++17
99.56 / 100
9 ms848 KiB
#include "mushrooms.h" #include <bits/stdc++.h> #define vi vector<int> #define pb push_back using namespace std; const int maxn = 20000; vi shroom[2] = {{0},{}}; int uses = 0; int type[maxn] = {0}; void found(int ind, int val) { type[ind] = val; shroom[val].pb(ind); } void start(int sec) { //test A_ vi test = {0,sec}; int res = use_machine(test); ++uses; found(sec,res); } void start2(vi probe) { //test A_A_ vi test; int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; int opp = !cur; for (int i=0; i<2; ++i) { test.pb(shroom[cur][i]); test.pb(probe[i]); } int res = use_machine(test); ++uses; int l = probe[0], r = probe[1]; if (res%2 == 0) { found(r,cur); } else { found(r,opp); --res; } if (res == 0) { found(l,cur); } else { found(l,opp); } } int quad(vi probe) { //test A_A_A_A_ vi test; int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; int opp = !cur; int k = probe.size(); for (int i=0; i<k; ++i) { test.pb(shroom[cur][i]); test.pb(probe[i]); } int res = use_machine(test); ++uses; int last = probe[k-1]; if (res%2 == 0) { found(last,cur); } else { found(last,opp); --res; } if (res == 0) { for (int i=0; i<k-1; ++i) { found(probe[i],cur); } } else if (res == 6) { for (int i=0; i<k-1; ++i) { found(probe[i],opp); } } return res; } void test1(vi probe) { //test A_A_A_A_ while we have less than 2 B's int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; int opp = !cur; int res = quad(probe); int l = probe[0], m = probe[1], r = probe[2]; if (res == 2) { vi subtest = {l,m}; start2(subtest); if (type[l] == cur && type[m] == cur) { found(r, opp); } else { found(r,cur); } } else if (res == 4) { vi subtest = {l,m}; start2(subtest); if (type[l] == opp && type[m] == opp) { found(r,cur); } else { found(r,opp); } } } void subtest2(vi probe, int cur) { //test A_A__B if we know probe is a permutation of (ABB) //test B_B__A if (AAB) //future george here: YOU FORGOT THE FREE SHROOM vi test; int opp = !cur; int l = probe[0], m = probe[1], r = probe[2], rr = probe[3]; test = {shroom[cur][0], l, shroom[cur][1], m, r, shroom[opp][0], rr}; int res = use_machine(test); ++uses; if (res%2 == 0) { found(rr,cur); --res; } else { found(rr,opp); } if (res == 1) { found(l,cur); found(m,opp); found(r,opp); } else if (res == 3) { found(l,opp); found(m,cur); found(r,opp); } else if (res == 5) { found(l,opp); found(m,opp); found(r,cur); } return; } bool test2(vi probe) { //test A_A_A_A_ when we already have 2 B's //future george here: YOU FORGOT THE FREE SHROOM vi test = probe; test.pop_back(); int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; int opp = !cur; int res = quad(test); //forgot case res 0, res 6 - free shroom is lost //fixed with bool - true if we are instantly done test.pop_back(); test.pb(probe.back()); if (res == 2) { subtest2(test, opp); return false; } else if (res == 4) { subtest2(test, cur); return false; } return true; } int test3(vi probe) { //test A_A_A_......A_A_ vi test; int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; int opp = !cur; int k = probe.size(); for (int i=0; i<k; ++i) { test.pb(shroom[cur][i]); test.pb(probe[i]); } int res = use_machine(test); ++uses; int last = probe[k-1]; if (res%2 == 0) { found(last,cur); } else { found(last,opp); --res; } int numcur = res/2; if (cur == 0) { return k-1-numcur; } return numcur; } int count_mushrooms(int n) { int count_a = 0; int magic = 90; for (int i=0; i<n; ++i) { type[i] = -1; } if (n <= 221) { for (int i = 1; i<n; ++i) { start(i); } return shroom[0].size(); } int ind = 1; while (shroom[0].size() < 2 && shroom[1].size()<2) { start(ind); ++ind; } while (shroom[0].size() < 4 && shroom[1].size()<4) { vi probe = {ind, ind+1}; start2(probe); ind +=2; } int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; int opp = !cur; while (shroom[opp].size() < 2 && shroom[cur].size() < magic) { vi probe; for (int i=0; i<4; ++i) { probe.pb(ind); ++ind; } test1(probe); } cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; opp = !cur; while (shroom[cur].size() < magic) { vi probe; for (int i=0; i<5; ++i) { probe.pb(ind); ++ind; } bool quick = test2(probe); if (quick) { --ind; //if the first 3 are the same, we don't need an extra check just for the last free shroom, just do it in the next batch } cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; opp = !cur; // cout << "excluding ind " << ind << " we found " << shroom[0].size() << "\n"; } int s = shroom[0].size(); while (ind != n) { cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1; opp = !cur; int s = shroom[cur].size(); int cap = min(s, n-ind); vi probe; for (int i=0; i<cap; ++i) { probe.pb(ind); ++ind; } count_a += test3(probe); } return count_a + shroom[0].size(); }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:212:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  212 |     while (shroom[opp].size() < 2 && shroom[cur].size() < magic) {
      |                                      ~~~~~~~~~~~~~~~~~~~^~~~~~~
mushrooms.cpp:222:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  222 |     while (shroom[cur].size() < magic) {
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~~
mushrooms.cpp:236:9: warning: unused variable 's' [-Wunused-variable]
  236 |     int s = shroom[0].size();
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...