#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include "mushrooms.h"
using namespace std;
const int VAL = 144;
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 = 1; i < n; ++i)
v.push_back(i);
v.push_back(0);
for (int it = 0; it < 10; ++it) {
random_shuffle(v.begin(), v.end());
use_machine(v);
}
v.erase(0);
int ans = 0, pos = 0;
bool doNextSimple = false;
a.push_back(0); found.insert(0);
while (a.size() < VAL && b.size() < VAL && pos < (int) v.size()) {
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()) arr.push_back(v[pos]), ++pos, ++used;
else break;
}
int ret = use_machine(arr);
int diff = (ret / 2) + (ret & 1);
ans += used - diff;
}
} 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()) arr.push_back(v[pos]), ++pos, ++used;
else break;
}
int ret = use_machine(arr);
int diff = (ret / 2) + (ret & 1);
ans += diff;
}
}
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
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:56:12: error: no matching function for call to 'std::vector<int>::erase(int)'
56 | v.erase(0);
| ^
In file included from /usr/include/c++/9/vector:67,
from mushrooms.cpp:2:
/usr/include/c++/9/bits/stl_vector.h:1427:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(std::vector<_Tp, _Alloc>::const_iterator) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*]'
1427 | erase(const_iterator __position)
| ^~~~~
/usr/include/c++/9/bits/stl_vector.h:1427:28: note: no known conversion for argument 1 from 'int' to 'std::vector<int>::const_iterator' {aka '__gnu_cxx::__normal_iterator<const int*, std::vector<int> >'}
1427 | erase(const_iterator __position)
| ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1454:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::const_iterator) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*]'
1454 | erase(const_iterator __first, const_iterator __last)
| ^~~~~
/usr/include/c++/9/bits/stl_vector.h:1454:7: note: candidate expects 2 arguments, 1 provided
