Submission #303492

#	Time	Username	Problem	Language	Result	Execution time	Memory
303492		rama_pang	Counting Mushrooms (IOI20_mushrooms)	C++14	100 / 100	19 ms	1408 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

int count_mushrooms(int n) {
  const auto Solve = [&](int size_limit) {
    int ans = 1;

    set<int> unknown;
    for (int i = 1; i < n; i++) {
      unknown.emplace(i);
    }
    vector<int> A, B;
    A.emplace_back(0);

    while (!unknown.empty() && (int) max(A.size(), B.size()) < size_limit) {
      if (unknown.size() == 1 || max(A.size(), B.size()) == 1) {
        // query A?
        // can identify ?
        int u = *begin(unknown);
        unknown.erase(u);
        if (use_machine({0, u}) == 1) {
          B.emplace_back(u);
        } else {
          A.emplace_back(u);
          ans += 1;
        }
      } else if (unknown.size() < 5 || max(A.size(), B.size()) < 3 || min(A.size(), B.size()) < 2) {
        // query A?A?
        // can identify both ?
        bool swapped = A.size() < 2;
        if (swapped) {
          swap(A, B);
        }

        int u = *begin(unknown);
        unknown.erase(u);
        int v = *begin(unknown);
        unknown.erase(v);

        int q = use_machine({A[0], u, A[1], v});
        if (q == 0) {
          A.emplace_back(u);
          A.emplace_back(v);
          ans += swapped ? 0 : 2;
        } else if (q == 1) {
          A.emplace_back(u);
          B.emplace_back(v);
          ans += 1;
        } else if (q == 2) {
          B.emplace_back(u);
          A.emplace_back(v);
          ans += 1;
        } else if (q == 3) {
          B.emplace_back(u);
          B.emplace_back(v);
          ans += swapped ? 2 : 0;
        }
        if (swapped) {
          swap(A, B);
        }
      } else {
        // query A?A?A?
        // if first and second ? is the same, can uniquely identify them
        // otherwise, query B?BA?A?A?, where the first and second ? is the
        // same as previously, and other 2 is new element
        // can uniquely identify all of them
        int oldA = A.size();
        bool swapped = A.size() < B.size();
        if (swapped) {
          swap(A, B);
        }

        int u = *begin(unknown);
        unknown.erase(u);
        int v = *begin(unknown);
        unknown.erase(v);
        int w = *begin(unknown);
        unknown.erase(w);

        int q = use_machine({A[0], u, A[1], v, A[2], w});
        if (q & 1) {
          q--;
          B.emplace_back(w);
        } else {
          A.emplace_back(w);
        }
        if (q == 0) {
          A.emplace_back(u);
          A.emplace_back(v);
        } else if (q == 4) {
          B.emplace_back(u);
          B.emplace_back(v);
        } else {
          int c = *begin(unknown);
          unknown.erase(c);
          int d = *begin(unknown);
          unknown.erase(d); 
          q = use_machine({B[0], u, B[1], A[0], v, A[1], c, A[2], d}) - 1;
          if (q & 1) {
            B.emplace_back(d);
          } else {
            A.emplace_back(d);
          }
          if (q & 2) {
            B.emplace_back(c);
          } else {
            A.emplace_back(c);
          }
          if (q & 4) {
            A.emplace_back(u);
            B.emplace_back(v);
          } else {
            B.emplace_back(u);
            A.emplace_back(v);
          }
        }
        if (swapped) {
          swap(A, B);
        }
        ans += int(A.size()) - oldA;
      }
    }

    while (!unknown.empty()) {
      bool swapped = A.size() < B.size();
      if (swapped) {
        swap(A, B);
      }
      vector<int> que;
      for (auto i : A) {
        que.emplace_back(i);
        que.emplace_back(*begin(unknown));
        unknown.erase(begin(unknown));
        if (unknown.empty()) {
          break;
        }
      }
      int q = use_machine(que);
      ans += swapped ? ((q + 1) / 2) : (int(que.size()) / 2 - (q + 1) / 2);
      if (q & 1) {
        B.emplace_back(que.back());
      } else {
        A.emplace_back(que.back());
      }
      if (swapped) {
        swap(A, B);
      }
    }
    return ans;
  };
  
  return Solve(100);
}

• Subtask 1: 100 / 100