Skip to content

Instantly share code, notes, and snippets.

@oToToT

oToToT/102798I.cpp

Created October 7, 2021 19:29
Show Gist options
  • Save oToToT/49ccbdd7ce599d7d176936f2683828cf to your computer and use it in GitHub Desktop.
Save oToToT/49ccbdd7ce599d7d176936f2683828cf to your computer and use it in GitHub Desktop.
Download ZIP
clang miscompilation??
Raw
102798I.cpp
// problem link: https://codeforces.com/gym/102798/problem/I
#include <bits/stdc++.h>
using namespace std;
template <uint64_t x, size_t n>
struct Pow {
uint64_t v;
constexpr Pow(): v(1) {
for (size_t i = 0; i < n; ++i) v *= x;
}
operator uint64_t() const { return v; }
};
struct A;
template <size_t off>
struct A_view {
A *a;
A_view(A *);
A_view() = delete;
A_view(A_view &&) = delete;
A_view(const A_view &) = delete;
operator int() const;
void operator=(int);
};
struct A {
uint64_t state;
template <size_t x>
A_view<x> val() {
return A_view<x>(this);
}
bool operator<(const A &rhs) const {
return state < rhs.state;
}
bool operator==(const A &rhs) const {
return state == rhs.state;
}
};
template <size_t off>
A_view<off>::A_view(A *a_) : a(a_) {}
template <size_t off>
A_view<off>::operator int() const {
return a->state / Pow<6, off>() % 6;
}
template <size_t off>
void A_view<off>::operator=(int x) {
a->state += x * Pow<6, off>() - a->state / Pow<6, off>() % 6 * Pow<6, off>();
}
ostream &operator<<(ostream &os, A a) {
os << " " << int(a.val<0>()) << int(a.val<1>()) << '\n';
os << " " << int(a.val<2>()) << int(a.val<3>()) << '\n';
os << int(a.val<4>()) << int(a.val<5>()) << int(a.val<8>()) << int(a.val<9>()) << int(a.val<12>()) << int(a.val<13>()) << int(a.val<20>()) << int(a.val<21>()) << '\n';
os << int(a.val<6>()) << int(a.val<7>()) << int(a.val<10>()) << int(a.val<11>()) << int(a.val<14>()) << int(a.val<15>()) << int(a.val<22>()) << int(a.val<23>()) << '\n';
os << " " << int(a.val<16>()) << int(a.val<17>()) << '\n';
os << " " << int(a.val<18>()) << int(a.val<19>()) << '\n';
return os;
}
int c2i[256];
static constexpr int rot[6][12] = {
{4, 5, 8, 9, 12, 13, 20, 21, 0, 2, 3, 1},
{6, 7, 10, 11, 14, 15, 22, 23, 16, 17, 19, 18},
{0, 2, 8, 10, 16, 18, 23, 21, 5, 7, 6, 4},
{1, 3, 9, 11, 17, 19, 22, 20, 12, 14, 15, 13},
{7, 5, 2, 3, 12, 14, 17, 16, 8, 9, 11, 10},
{6, 4, 0, 1, 13, 15, 19, 18, 23, 21, 20, 22}
};
template <int id>
static A rt(const A &a) {
A r = a;
if constexpr (id < 6) {
int x = r.val<rot[id][0]>();
int y = r.val<rot[id][1]>();
r.val<rot[id][0]>() = int(r.val<rot[id][0 + 2]>());
r.val<rot[id][1]>() = int(r.val<rot[id][1 + 2]>());
r.val<rot[id][2]>() = int(r.val<rot[id][2 + 2]>());
r.val<rot[id][3]>() = int(r.val<rot[id][3 + 2]>());
r.val<rot[id][4]>() = int(r.val<rot[id][4 + 2]>());
r.val<rot[id][5]>() = int(r.val<rot[id][5 + 2]>());
r.val<rot[id][6]>() = x;
r.val<rot[id][7]>() = y;
int z = r.val<rot[id][8]>();
r.val<rot[id][8 + 0]>() = int(r.val<rot[id][8 + 0 + 1]>());
r.val<rot[id][8 + 1]>() = int(r.val<rot[id][8 + 1 + 1]>());
r.val<rot[id][8 + 2]>() = int(r.val<rot[id][8 + 2 + 1]>());
r.val<rot[id][11]>() = z;
} else {
constexpr int nid = id - 6;
int x = r.val<rot[nid][6]>();
int y = r.val<rot[nid][7]>();
r.val<rot[nid][5 + 2]>() = int(r.val<rot[nid][5]>());
r.val<rot[nid][4 + 2]>() = int(r.val<rot[nid][4]>());
r.val<rot[nid][3 + 2]>() = int(r.val<rot[nid][3]>());
r.val<rot[nid][2 + 2]>() = int(r.val<rot[nid][2]>());
r.val<rot[nid][1 + 2]>() = int(r.val<rot[nid][1]>());
r.val<rot[nid][0 + 2]>() = int(r.val<rot[nid][0]>());
r.val<rot[nid][0]>() = x;
r.val<rot[nid][1]>() = y;
int z = r.val<rot[nid][11]>();
r.val<rot[nid][8 + 2 + 1]>() = int(r.val<rot[nid][8 + 2]>());
r.val<rot[nid][8 + 1 + 1]>() = int(r.val<rot[nid][8 + 1]>());
r.val<rot[nid][8 + 0 + 1]>() = int(r.val<rot[nid][8 + 0]>());
r.val<rot[nid][8]>()= z;
}
return r;
}
static A minimal(A a) {
A r = a;
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
a = rt<2>(a);
a = rt<3>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
a = rt<2>(a);
a = rt<3>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
a = rt<2>(a);
a = rt<3>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
a = rt<2>(a);
a = rt<3>(a);
a = rt<4>(a);
a = rt<5>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
a = rt<4>(a);
a = rt<5>(a);
a = rt<4>(a);
a = rt<5>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
a = rt<0>(a);
a = rt<1>(a);
r = min(r, a);
return r;
}
struct myhash {
uint64_t operator()(const A &a) const { return a.state; }
};
unordered_map<A, int, myhash> d;
void solve() {
string l[6];
{
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
l[0] = " " + s1 + " " + s2 + " " + s3;
}
{
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
l[1] = " " + s1 + " " + s2 + " " + s3;
}
cin >> l[2];
cin >> l[3];
{
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
l[4] = " " + s1 + " " + s2 + " " + s3;
}
{
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
l[5] = " " + s1 + " " + s2 + " " + s3;
}
A s, t;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wchar-subscripts"
s.val< 0>() = c2i[l[0][2]];
s.val< 1>() = c2i[l[0][3]];
s.val< 2>() = c2i[l[1][2]];
s.val< 3>() = c2i[l[1][3]];
s.val< 4>() = c2i[l[2][0]];
s.val< 5>() = c2i[l[2][1]];
s.val< 6>() = c2i[l[3][0]];
s.val< 7>() = c2i[l[3][1]];
s.val< 8>() = c2i[l[2][2]];
s.val< 9>() = c2i[l[2][3]];
s.val<10>() = c2i[l[3][2]];
s.val<11>() = c2i[l[3][3]];
s.val<12>() = c2i[l[2][4]];
s.val<13>() = c2i[l[2][5]];
s.val<14>() = c2i[l[3][4]];
s.val<15>() = c2i[l[3][5]];
s.val<16>() = c2i[l[4][2]];
s.val<17>() = c2i[l[4][3]];
s.val<18>() = c2i[l[5][2]];
s.val<19>() = c2i[l[5][3]];
s.val<20>() = c2i[l[2][6]];
s.val<21>() = c2i[l[2][7]];
s.val<22>() = c2i[l[3][6]];
s.val<23>() = c2i[l[3][7]];
t.val< 0>() = c2i[l[0][9 + 2]];
t.val< 1>() = c2i[l[0][9 + 3]];
t.val< 2>() = c2i[l[1][9 + 2]];
t.val< 3>() = c2i[l[1][9 + 3]];
t.val< 4>() = c2i[l[2][9 + 0]];
t.val< 5>() = c2i[l[2][9 + 1]];
t.val< 6>() = c2i[l[3][9 + 0]];
t.val< 7>() = c2i[l[3][9 + 1]];
t.val< 8>() = c2i[l[2][9 + 2]];
t.val< 9>() = c2i[l[2][9 + 3]];
t.val<10>() = c2i[l[3][9 + 2]];
t.val<11>() = c2i[l[3][9 + 3]];
t.val<12>() = c2i[l[2][9 + 4]];
t.val<13>() = c2i[l[2][9 + 5]];
t.val<14>() = c2i[l[3][9 + 4]];
t.val<15>() = c2i[l[3][9 + 5]];
t.val<16>() = c2i[l[4][9 + 2]];
t.val<17>() = c2i[l[4][9 + 3]];
t.val<18>() = c2i[l[5][9 + 2]];
t.val<19>() = c2i[l[5][9 + 3]];
t.val<20>() = c2i[l[2][9 + 6]];
t.val<21>() = c2i[l[2][9 + 7]];
t.val<22>() = c2i[l[3][9 + 6]];
t.val<23>() = c2i[l[3][9 + 7]];
#pragma GCC diagnostic pop
s = minimal(s);
t = minimal(t);
while (int dd = d[s]) {
bool done = false;
if (not done) {
constexpr int i = 0;
auto ns = minimal(rt<i>(s));
if (d[ns] == dd - 1) {
t = minimal(rt<(i + 6) % 12>(t));
s = ns;
done = true;
}
}
if (not done) {
constexpr int i = 2;
auto ns = minimal(rt<i>(s));
if (d[ns] == dd - 1) {
t = minimal(rt<(i + 6) % 12>(t));
s = ns;
done = true;
}
}
if (not done) {
constexpr int i = 4;
auto ns = minimal(rt<i>(s));
if (d[ns] == dd - 1) {
t = minimal(rt<(i + 6) % 12>(t));
s = ns;
done = true;
}
}
if (not done) {
constexpr int i = 6;
auto ns = minimal(rt<i>(s));
if (d[ns] == dd - 1) {
t = minimal(rt<(i + 6) % 12>(t));
s = ns;
done = true;
}
}
if (not done) {
constexpr int i = 8;
auto ns = minimal(rt<i>(s));
if (d[ns] == dd - 1) {
t = minimal(rt<(i + 6) % 12>(t));
s = ns;
done = true;
}
}
if (not done) {
constexpr int i = 10;
auto ns = minimal(rt<i>(s));
if (d[ns] == dd - 1) {
t = minimal(rt<(i + 6) % 12>(t));
s = ns;
done = true;
}
}
}
cout << d[t] << '\n';
}
void predo() {
d.reserve(5000000);
A s;
s.state = 26365617934983710LLU;
d[s] = 0;
queue<A> bfs;
bfs.push(s);
while (not bfs.empty()) {
auto x = bfs.front();
bfs.pop();
const int dd = d[x];
{
constexpr int i = 0;
auto nx = minimal(rt<i>(x));
if (d.find(nx) == d.end()) {
d[nx] = dd + 1;
bfs.emplace(nx);
}
}
{
constexpr int i = 2;
auto nx = minimal(rt<i>(x));
if (d.find(nx) == d.end()) {
d[nx] = dd + 1;
bfs.emplace(nx);
}
}
{
constexpr int i = 4;
auto nx = minimal(rt<i>(x));
if (d.find(nx) == d.end()) {
d[nx] = dd + 1;
bfs.emplace(nx);
}
}
{
constexpr int i = 6;
auto nx = minimal(rt<i>(x));
if (d.find(nx) == d.end()) {
d[nx] = dd + 1;
bfs.emplace(nx);
}
}
{
constexpr int i = 8;
auto nx = minimal(rt<i>(x));
if (d.find(nx) == d.end()) {
d[nx] = dd + 1;
bfs.emplace(nx);
}
}
{
constexpr int i = 10;
auto nx = minimal(rt<i>(x));
if (d.find(nx) == d.end()) {
d[nx] = dd + 1;
bfs.emplace(nx);
}
}
if (d.size() % 1000 == 0) cout << "dsz = " << d.size() << endl;
}
cout << "done" << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
predo();
c2i['G'] = 0;
c2i['O'] = 1;
c2i['Y'] = 2;
c2i['R'] = 3;
c2i['W'] = 4;
c2i['B'] = 5;
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment