Submission #304306

#	Time	Username	Problem	Language	Result	Execution time	Memory
304306		Fdg	Counting Mushrooms (IOI20_mushrooms)	C++14	97.84 / 100	14 ms	640 KiB

mushrooms

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include "mushrooms.h"

using namespace std;

const int VAL = 112;

vector<int> a, b, missing;

map<int, vector<int>> diff, eq;
set<int> found;

void nextPos(const vector<int>& v, int& pos) {
  while (pos < (int) v.size()) {
    if (found.count(v[pos])) {
      ++pos;
    } else break;
  }
}

void process(int x, bool isA) {
  if (found.count(x)) return;
  found.insert(x);

  if (isA) a.push_back(x);
  else b.push_back(x);

  if (diff.count(x))
    for (int val : diff[x]) {
      process(val, !isA);
    }

  if (eq.count(x))
    for (int val : eq[x]) {
      process(val, isA);
    }
}

int count_mushrooms(int n) {
  a.clear(); b.clear(); diff.clear(); found.clear(); missing.clear();

  srand(time(NULL));
  vector<int> v;
  // for (int i = 0; i < n; ++i)
  //   v.push_back(i);
  // for (int it = 0; it < 1; ++it) {
  //   random_shuffle(v.begin(), v.end());
  //   use_machine(v);
  // }

  v.clear();
  for (int i = 1; i < n; ++i)
    v.push_back(i);
  random_shuffle(v.begin(), v.end());

  v.push_back(0);
  use_machine(v);
  v.pop_back();

  int ans = 0, pos = 0;

  bool doNextSimple = false;

  double COEF = 1.2;
  int iter = 1;

  a.push_back(0); found.insert(0);
  while (a.size() < VAL && b.size() < VAL && pos < (int) v.size()) {
    // if (a.size() > 100 && a.size() > COEF * b.size()) break;
    // if (b.size() > 100 && b.size() > COEF * a.size()) break;

    if ((n - a.size() - b.size()) / max(a.size(), b.size()) + iter <= 226) break;
    ++iter;
    if (iter >= VAL) break;

    if (a.size() > 2) {
      vector<int> arr;
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(a[0]);
        arr.push_back(v[pos]), ++pos;
      }
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(a[1]);
        arr.push_back(v[pos]), ++pos; 
      }
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(a[2]);
        arr.push_back(v[pos]), ++pos; 
      }

      doNextSimple = false;
      int ret = use_machine(arr);
      if (arr.size() == 2) {
        if (ret == 1) {
          process(arr[1], false);
        } else {
          process(arr[1], true);
        }
      } else if (arr.size() == 4) {
        if (ret == 3) {
          process(arr[1], false);
          process(arr[3], false);
        } else if (ret == 2) {
          process(arr[1], false);
          process(arr[3], true);
        } else if (ret == 1) {
          process(arr[1], true);
          process(arr[3], false); 
        } else {
          process(arr[1], true);
          process(arr[3], true);
        }
      } else if (arr.size() == 6) {
        if (ret == 5) {
          process(arr[1], false);
          process(arr[3], false);
          process(arr[5], false);
        } else if (ret == 4) {
          process(arr[1], false);
          process(arr[3], false);
          process(arr[5], true);
        } else if (ret == 3) {
          process(arr[5], false);
          diff[arr[1]].push_back(arr[3]);
          diff[arr[3]].push_back(arr[1]);
          missing.push_back(arr[1]);
          --pos;
          v[pos] = arr[3];
          if (pos + 2 < (int) v.size()) swap(v[pos], v[pos + 2]);
          doNextSimple = true;
        } else if (ret == 2) {
          process(arr[5], true);
          diff[arr[1]].push_back(arr[3]);
          diff[arr[3]].push_back(arr[1]);
          missing.push_back(arr[1]);
          --pos;
          v[pos] = arr[3];
          if (pos + 2 < (int) v.size()) swap(v[pos], v[pos + 2]);
          doNextSimple = true;
        } else if (ret == 1) {
          process(arr[1], true);
          process(arr[3], true);
          process(arr[5], false);
        } else {
          process(arr[1], true);
          process(arr[3], true);
          process(arr[5], true);
        }
      }
    } else if (b.size() > 2) {
      vector<int> arr;
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(b[0]);
        arr.push_back(v[pos]), ++pos;
      }
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(b[1]);
        arr.push_back(v[pos]), ++pos; 
      }
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(b[2]);
        arr.push_back(v[pos]), ++pos; 
      }

      doNextSimple = false;
      int ret = use_machine(arr);
      if (arr.size() == 2) {
        if (ret == 1) {
          process(arr[1], true);
        } else {
          process(arr[1], false);
        }
      } else if (arr.size() == 4) {
        if (ret == 3) {
          process(arr[1], true);
          process(arr[3], true);
        } else if (ret == 2) {
          process(arr[1], true);
          process(arr[3], false);
        } else if (ret == 1) {
          process(arr[1], false);
          process(arr[3], true); 
        } else {
          process(arr[1], false);
          process(arr[3], false);
        }
      } else if (arr.size() == 6) {
        if (ret == 5) {
          process(arr[1], true);
          process(arr[3], true);
          process(arr[5], true);
        } else if (ret == 4) {
          process(arr[1], true);
          process(arr[3], true);
          process(arr[5], false);
        } else if (ret == 3) {
          process(arr[5], true);
          diff[arr[1]].push_back(arr[3]);
          diff[arr[3]].push_back(arr[1]);
          missing.push_back(arr[3]);
          --pos;
          v[pos] = arr[1];
          if (pos + 2 < (int) v.size()) swap(v[pos], v[pos + 2]);
          doNextSimple = true;
        } else if (ret == 2) {
          process(arr[5], false);
          diff[arr[1]].push_back(arr[3]);
          diff[arr[3]].push_back(arr[1]);
          missing.push_back(arr[3]);
          --pos;
          v[pos] = arr[1];
          if (pos + 2 < (int) v.size()) swap(v[pos], v[pos + 2]);
          doNextSimple = true;
        } else if (ret == 1) {
          process(arr[1], false);
          process(arr[3], false);
          process(arr[5], true);
        } else {
          process(arr[1], false);
          process(arr[3], false);
          process(arr[5], false);
        }
      }
    } else

    /*if (a.size() > 1) {
      vector<int> arr;
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(v[pos]), ++pos;
        arr.push_back(a[0]);
      }
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(v[pos]), ++pos;
        arr.push_back(a[1]); 
      }
      if (!doNextSimple) {
        nextPos(v, pos);
        if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos;
      }

      doNextSimple = false;
      int ret = use_machine(arr);
      if (arr.size() == 2) {
        if (ret == 1) {
          process(arr[0], false);
        } else {
          process(arr[0], true);
        }
      } else if (arr.size() == 4) {
        if (ret == 3) {
          process(arr[0], false);
          process(arr[2], false);
        } else if (ret == 2) {
          process(arr[0], true);
          process(arr[2], false);
        } else if (ret == 1) {
          process(arr[0], false);
          process(arr[2], true); 
        } else {
          process(arr[0], true);
          process(arr[2], true);
        }
      } else if (arr.size() == 5) {
        if (ret == 4) {
          process(arr[0], false);
          process(arr[2], false);
          process(arr[4], false);
        } else if (ret == 3) {
          process(arr[2], false);
          diff[arr[0]].push_back(arr[4]);
          diff[arr[4]].push_back(arr[0]);
          missing.push_back(arr[4]);
          --pos;
          v[pos] = arr[0];
          if (pos + 1 < (int) v.size()) swap(v[pos], v[pos + 1]);
          doNextSimple = true;
        } else if (ret == 2) {
          diff[arr[0]].push_back(arr[2]);
          diff[arr[2]].push_back(arr[0]);
          diff[arr[4]].push_back(arr[2]);
          diff[arr[2]].push_back(arr[4]);
          eq[arr[0]].push_back(arr[4]);
          eq[arr[4]].push_back(arr[0]);
          missing.push_back(arr[0]);
          missing.push_back(arr[4]);
          --pos;
          v[pos] = arr[2];
          if (pos + 1 < (int) v.size()) swap(v[pos], v[pos + 1]);
          doNextSimple = true;
        } else if (ret == 1) {
          process(arr[2], true);
          diff[arr[0]].push_back(arr[4]);
          diff[arr[4]].push_back(arr[0]);
          missing.push_back(arr[4]);
          --pos;
          v[pos] = arr[0];
          if (pos + 1 < (int) v.size()) swap(v[pos], v[pos + 1]);
          doNextSimple = true;
        } else {
          process(arr[0], true);
          process(arr[2], true);
          process(arr[4], true);
        }
      }
    } else if (b.size() > 1) {
      vector<int> arr;
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(v[pos]), ++pos;
        arr.push_back(b[0]);
      }
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(v[pos]), ++pos;
        arr.push_back(b[1]); 
      }
      if (!doNextSimple) {
        nextPos(v, pos);
        if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos;
      }

      doNextSimple = false;
      int ret = use_machine(arr);
      if (arr.size() == 2) {
        if (ret == 1) {
          process(arr[0], true);
        } else {
          process(arr[0], false);
        }
      } else if (arr.size() == 4) {
        if (ret == 3) {
          process(arr[0], true);
          process(arr[2], true);
        } else if (ret == 2) {
          process(arr[0], false);
          process(arr[2], true);
        } else if (ret == 1) {
          process(arr[0], true);
          process(arr[2], false); 
        } else {
          process(arr[0], false);
          process(arr[2], false);
        }
      } else if (arr.size() == 5) {
        if (ret == 4) {
          process(arr[0], true);
          process(arr[2], true);
          process(arr[4], true);
        } else if (ret == 3) {
          process(arr[2], true);
          diff[arr[0]].push_back(arr[4]);
          diff[arr[4]].push_back(arr[0]);
          missing.push_back(arr[4]);
          --pos;
          v[pos] = arr[0];
          if (pos + 1 < (int) v.size()) swap(v[pos], v[pos + 1]);
          doNextSimple = true;
        } else if (ret == 2) {
          diff[arr[0]].push_back(arr[2]);
          diff[arr[2]].push_back(arr[0]);
          diff[arr[4]].push_back(arr[2]);
          diff[arr[2]].push_back(arr[4]);
          eq[arr[0]].push_back(arr[4]);
          eq[arr[4]].push_back(arr[0]);
          missing.push_back(arr[0]);
          missing.push_back(arr[4]);
          --pos;
          v[pos] = arr[2];
          if (pos + 1 < (int) v.size()) swap(v[pos], v[pos + 1]);
          doNextSimple = true;
        } else if (ret == 1) {
          process(arr[2], false);
          diff[arr[0]].push_back(arr[4]);
          diff[arr[4]].push_back(arr[0]);
          missing.push_back(arr[4]);
          --pos;
          v[pos] = arr[0];
          if (pos + 1 < (int) v.size()) swap(v[pos], v[pos + 1]);
          doNextSimple = true;
        } else {
          process(arr[0], false);
          process(arr[2], false);
          process(arr[4], false);
        }
      }
    } else */{
      vector<int> arr = {a[0]};
      nextPos(v, pos);
      if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos;
      else break;

      doNextSimple = false;
      int ret = use_machine(arr);
      if (ret & 1) {
        process(arr[1], false);
      } else {
        process(arr[1], true);
      }
    }
  }

  ans = a.size();

  // if (a.size() + b.size() != n) exit(-1);

  for (int x : missing) {
    if (!found.count(x))
      v.push_back(x);
  }

  if (a.size() >= b.size()) {
    while (pos < (int) v.size()) {
      vector<int> arr;
      int used = 0;
      for (int i = 0; i < (int) a.size(); ++i) {
        arr.push_back(a[i]);
        nextPos(v, pos);
        if (pos < (int) v.size()) {
          if (i + 1 == (int) a.size()) {
            arr.push_back(v.back());
            v.pop_back();
          } else {
            arr.push_back(v[pos]), ++pos;
          }
          ++used;
        } else break;
      }
      int ret = use_machine(arr);
      int diff = (ret / 2) + (ret & 1);
      ans += used - diff;
      if (ret & 1) {
        b.push_back(arr.back());
      } else {
        a.push_back(arr.back());
      }
    }
  } else {
    while (pos < (int) v.size()) {
      vector<int> arr;
      int used = 0;
      for (int i = 0; i < (int) b.size(); ++i) {
        arr.push_back(b[i]);
        nextPos(v, pos);
        if (pos < (int) v.size()) {
          if (i + 1 == (int) b.size()) {
            arr.push_back(v.back());
            v.pop_back();
          } else {
            arr.push_back(v[pos]), ++pos;
          }
          ++used;
        } else break;
      }
      int ret = use_machine(arr);
      int diff = (ret / 2) + (ret & 1);
      ans += diff;
      if (ret & 1) {
        a.push_back(arr.back());
      } else {
        b.push_back(arr.back());
      }
    }
  }

  return ans;
}

// int count_mushrooms(int n) {
//   int ans = 1;
//   for (int i = 1; i < n; i += 2) {
//     vector<int> v;
//     if (i + 1 < n) v = {i, 0, i + 1};
//     else v = {i, 0};
//     int ret = use_machine(v);
//     ans += (v.size() - 1) - ret;
//   }
//   return ans;
// }

// int main() {
//   ios::sync_with_stdio(false);

//   return 0; 
// }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:66:8: warning: variable 'doNextSimple' set but not used [-Wunused-but-set-variable]
   66 |   bool doNextSimple = false;
      |        ^~~~~~~~~~~~
mushrooms.cpp:68:10: warning: unused variable 'COEF' [-Wunused-variable]
   68 |   double COEF = 1.2;
      |          ^~~~

• Subtask 1: 97.8355 / 100