/*
________ ___ ________ ________ ________ ___ ________ ________ ________
|\ ____\|\ \|\ ____\|\ __ \ |\ ___ \|\ \|\ ____\|\ ____\|\ __ \
\ \ \___|\ \ \ \ \___|\ \ \|\ \ \ \ \\ \ \ \ \ \ \___|\ \ \___|\ \ \|\ \
\ \ \ __\ \ \ \ \ __\ \ __ \ \ \ \\ \ \ \ \ \ \ __\ \ \ __\ \ __ \
\ \ \|\ \ \ \ \ \|\ \ \ \ \ \ \ \ \\ \ \ \ \ \ \|\ \ \ \|\ \ \ \ \ \
\ \_______\ \__\ \_______\ \__\ \__\ \ \__\\ \__\ \__\ \_______\ \_______\ \__\ \__\
\|_______|\|__|\|_______|\|__|\|__| \|__| \|__|\|__|\|_______|\|_______|\|__|\|__|
________ ________ ________ ________ ___ ___ ________ _________ ___ ________ ________
|\ __ \|\ __ \|\ __ \|\ ___ \|\ \|\ \|\ ____\\___ ___\\ \|\ __ \|\ ___ \
\ \ \|\ \ \ \|\ \ \ \|\ \ \ \_|\ \ \ \\\ \ \ \___\|___ \ \_\ \ \ \ \|\ \ \ \\ \ \
\ \ ____\ \ _ _\ \ \\\ \ \ \ \\ \ \ \\\ \ \ \ \ \ \ \ \ \ \ \\\ \ \ \\ \ \
\ \ \___|\ \ \\ \\ \ \\\ \ \ \_\\ \ \ \\\ \ \ \____ \ \ \ \ \ \ \ \\\ \ \ \\ \ \
\ \__\ \ \__\\ _\\ \_______\ \_______\ \_______\ \_______\ \ \__\ \ \__\ \_______\ \__\\ \__\
\|__| \|__|\|__|\|_______|\|_______|\|_______|\|_______| \|__| \|__|\|_______|\|__| \|__|
Written by: giga nigga
*/
// #include "largest.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "scales.h"
const int N = 720, INF = 1e9;
vector<array<int, 6>> perm_list;
bitset<N> edge[6][6][6][3][3];
bitset<N> sigma[6][6][6][6][3];
const int D = 6;
int po[10];
int dfs(bitset<N> u, int depth){
int cnt = u.count();
if (cnt == 1) return depth;
if (depth == D) return INF;
for(int i = 0; i < 6; ++i) for(int j = i + 1; j < 6; ++j) for(int k = j+1; k < 6; ++k)
for(int x = 0; x < 3; ++x) {
int ans = 0, valid_cnt = 0;
for(bitset<N> y: edge[i][j][k][x]){
bitset<N> nxt = u & y;
int cnt = nxt.count();
if (cnt == 0) continue;
if (cnt > po[5 - depth]) ans = INF;
valid_cnt++;
}
if (ans == INF || valid_cnt == 0) continue;
for(bitset<N> y: edge[i][j][k][x]){
bitset<N> nxt = u & y;
int cnt = nxt.count();
if (cnt == 0) continue;
maximize(ans, dfs(u & y, depth + 1));
if (ans == INF) break;
}
if (ans <= D) return ans;
}
for(int i= 0; i<6; ++i) for(int j= i+1; j < 6; ++j) for(int k = j+1; k < 6; ++k)
for(int t = 0; t < 6; ++t){
if (t == i || t == j || t == k) continue;
int ans = 0, valid_cnt = 0;
for(bitset<N> y: sigma[i][j][k][t]){
bitset<N> nxt = u & y;
int cnt = nxt.count();
if (cnt == 0) continue;
if (cnt > po[5 - depth]) ans = INF;
valid_cnt++;
}
if (ans == INF || valid_cnt == 0) continue;
for(bitset<N> y: sigma[i][j][k][t]){
bitset<N> nxt = u & y;
int cnt = nxt.count();
if (cnt == 0) continue;
maximize(ans, dfs(u & y, depth + 1));
if (ans == INF) break;
}
if (ans <= D) {
return ans;
}
}
return INF;
}
void init(int T){
po[0] = 1;
for(int i = 1; i < 10; ++i) po[i] = po[i-1] * 3;
array<int, 6> perm;
for(int i= 0; i < 6; ++i) perm[i] = i;
do{
perm_list.push_back(perm);
}while(next_permutation(ALL(perm)));
for(int i= 0; i<6; ++i) for(int j= i+1; j < 6; ++j) for(int k = j+1; k < 6; ++k){
array<int, 3> val = {{i, j, k}};
for(int p = 0; p < N; ++p){
array<int, 6> cur_perm = perm_list[p];
array<int, 3> pos = {{0, 1, 2}};
sort(ALL(pos), [&val, &cur_perm] (int x, int y){return cur_perm[val[x]] < cur_perm[val[y]];});
for(int x = 0; x < 3; ++x) {
edge[i][j][k][x][pos[x]][p] = 1;
}
}
}
for(int i= 0; i<6; ++i) for(int j= i+1; j < 6; ++j) for(int k = j+1; k < 6; ++k)
for(int t = 0; t < 6; ++t) {
if (t == i || t == j || t == k) continue;
array<int, 3> val = {{i, j, k}};
for(int p = 0; p < N; ++p){
array<int, 6> cur_perm = perm_list[p];
int mi = -1;
for(int x = 0; x< 3; ++x){
if (cur_perm[val[x]] > cur_perm[t]){
if (mi == -1 || cur_perm[val[x]] < cur_perm[val[mi]]){
mi = x;
}
}
}
if (mi == -1){
for(int x = 0; x< 3; ++x){
if (mi == -1 || cur_perm[val[x]] < cur_perm[val[mi]]){
mi = x;
}
}
}
sigma[i][j][k][t][mi][p] = 1;
}
}
bitset<N> sigma; sigma.set();
}
void orderCoins() {
bitset<N> u; u.set();
int depth = 0;
while(u.count() > 1){
bool found = false;
for(int i = 0; i < 6; ++i) for(int j = i + 1; j < 6; ++j) for(int k = j+1; k < 6; ++k)
for(int x = 0; x < 3; ++x) if (!found) {
int ans = 0, valid_cnt = 0;
for(bitset<N> y: edge[i][j][k][x]){
bitset<N> nxt = u & y;
int cnt = nxt.count();
if (cnt == 0) continue;
if (cnt > po[5 - depth]) ans = INF;
valid_cnt++;
}
if (ans == INF || valid_cnt == 0) continue;
for(bitset<N> y: edge[i][j][k][x]){
bitset<N> nxt = u & y;
int cnt = nxt.count();
if (cnt == 0) continue;
maximize(ans, dfs(u & y, depth + 1));
if (ans == INF) break;
}
if (ans <= D) {
found = true;
int cur;
if (x == 0) {
cur = getLightest(i+1, j+1, k+1);
}
else if (x == 1) cur = getMedian(i+1, j+1, k+1);
else cur = getHeaviest(i+1, j+1, k+1);
bitset<N> sech;
if (cur == i+1) sech = edge[i][j][k][x][0];
else if (cur == j+1) sech = edge[i][j][k][x][1];
else sech = edge[i][j][k][x][2];
u = u & sech;
}
}
for(int i= 0; i<6; ++i) for(int j= i+1; j < 6; ++j) for(int k = j+1; k < 6; ++k)
for(int t = 0; t < 6; ++t) if (!found){
if (t == i || t == j || t == k) continue;
int ans = 0, valid_cnt = 0;
for(bitset<N> y: sigma[i][j][k][t]){
bitset<N> nxt = u & y;
int cnt = nxt.count();
if (cnt == 0) continue;
if (cnt > po[5 - depth]) ans = INF;
valid_cnt++;
}
if (ans == INF || valid_cnt == 0) continue;
for(bitset<N> y: sigma[i][j][k][t]){
bitset<N> nxt = u & y;
int cnt = nxt.count();
if (cnt == 0) continue;
maximize(ans, dfs(u & y, depth + 1));
if (ans == INF) break;
}
if (ans <= D) {
found = true;
int cur = getNextLightest(i+1, j+1, k+1, t+1);
bitset<N> sech;
if (cur == i+1) sech = sigma[i][j][k][t][0];
else if (cur == j+1) sech = sigma[i][j][k][t][1];
else sech = sigma[i][j][k][t][2];
u = u & sech;
}
}
depth++;
}
int p = u._Find_first();
int ans[6];
memset(ans, 0, sizeof ans);
for(int i = 0; i < 6; ++i)
ans[perm_list[p][i]] = i+1;
answer(ans);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
