Create a gist now

Instantly share code, notes, and snippets.

search_piet5.cpp
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define FOR(i, a, b) \
for (int i = static_cast<int>(a); i < static_cast<int>(b); ++i)
#define ALL(f, x, ...) \
([&](decltype(x)& ALL) { \
return (f)(begin(ALL), end(ALL), ##__VA_ARGS__); \
})(x)
void ASYNC_IO() {
cin.tie(0);
ios::sync_with_stdio(false);
}
template <class IT>
bool next_combination(IT first1, IT last1, IT first2, IT last2) {
if ((first1 == last1) || (first2 == last2)) {
return false;
}
IT m1 = last1;
IT m2 = last2;
--m2;
while (--m1 != first1 && !(*m1 < *m2)) {
}
bool result = (m1 == first1) && !(*first1 < *m2);
if (!result) {
while (first2 != m2 && !(*m1 < *first2)) ++first2;
first1 = m1;
std::iter_swap(first1, first2);
++first1;
++first2;
}
if ((first1 != last1) && (first2 != last2)) {
m1 = last1;
m2 = first2;
while ((m1 != first1) && (m2 != last2)) {
std::iter_swap(--m1, m2);
++m2;
}
std::reverse(first1, m1);
std::reverse(first1, last1);
std::reverse(m2, last2);
std::reverse(first2, last2);
}
return !result;
}
template <class IT, typename INT>
bool next_combination(IT first, IT last, INT num) {
auto middle = first + num;
return next_combination(first, middle, middle, last);
}
template <typename INT>
vector<INT> combinations(INT last) {
vector<INT> data;
REP(i, last) data.push_back(i);
return data;
}
int order(int from, int to) {
// 0 <= from,to < 18
if (from % 3 != 0 && to % 3 == 0) to += 3;
if (from % 3 == 2 && to % 3 == 1) to += 3;
to -= (from % 3);
from -= (from % 3);
if (from > to) to += 18;
return to - from;
}
template <typename T>
vector<T> SLICE(const vector<T>& base, int begin = 0, int end = 0) {
if (end == 0) end = base.size();
vector<T> res;
FOR(i, begin, end) { res.push_back(base[i]); }
return res;
};
struct Info {
int num;
vector<int> orders, kinds;
bool is_same(const Info& info) const {
REP(i, orders.size()) if (orders[i] != info.orders[i]) return false;
return true;
}
};
signed main() {
ASYNC_IO();
auto data = combinations(18);
FOR(n, 4, 6) {
vector<Info> infos;
do {
vector<int> orders(18);
REP(j1, n) {
REP(j2, j1) {
auto regist = [&](int pos) {
// if (orders[pos] == 0)
orders[pos]++;
};
regist(order(data[j1], data[j2]));
regist(order(data[j2], data[j1]));
}
}
int res = 0;
for (auto order : orders) res += order > 0 ? 1 : 0;
Info info = {res, orders, SLICE(data, 0, n)};
if (infos.size() == 0) {
infos.push_back(info);
continue;
}
if (infos[0].num > info.num) continue;
if (infos[0].num < info.num) {
infos.clear();
infos.push_back(info);
continue;
}
if (!ALL(any_of, infos,
[&](const auto& it) { return it.is_same(info); })) {
infos.push_back(info);
continue;
}
} while (ALL(next_combination, data, n));
for (auto& info : infos) {
cout << info.num << "::";
for (auto kind : info.kinds) cout << kind << " ";
cout << endl;
REP(y, 3) {
REP(x, 6) {
if (ALL(any_of, info.kinds,
[&](const auto& it) { return it == 3 * x + y; })) {
cout << "o ";
} else {
cout << "x ";
}
}
cout << endl;
}
cout << endl;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment