#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int mx = 6;
map<vector<vector<int>>,int>mp;
map<vector<vector<int>>,pair<int,vector<int>>>mov;
vector<int> revers(vector<int>v){
vector<int>ans(mx);
for(int i = 0;i<mx;i++){
ans[v[i]]=i;
}
return ans;
}
vector<int> cop(vector<int>v){
vector<int>ans;
for(int i : v){
ans.push_back(i);
}
return ans;
}
int rec(vector<vector<int>>pos, int dep){
if(mp.find(pos)!=mp.end()){
if(mp[pos]==-1){
return 1e9;
}
return mp[pos];
}
if(pos.size()==1){
mp[pos]=0;
return mp[pos];
}
if(pos.size()==0){
mp[pos]=-1e9;
return mp[pos];
}
int req = 0;
for(int i = 0;i<mx;i++){
if(pow(3,i)<pos.size()){
req=i;
}
}
req++;
int nx = (int)pow(3,mx-dep);
mp[pos]=-1;
int ans = 1e9;
for(int a = 0;a<mx;a++){
for(int b = a+1;b<mx;b++){
for(int c = b+1;c<mx;c++){
if(ans<=req){
return (mp[pos]=ans+1);
}
int mov1 = 1e9;
int mov2 = 1e9;
int mov3 = 1e9;
int mov4 = 1e9;
int optd=-1;
//1st:
vector<vector<int>>curra,currb,currc;
for(vector<int>v:pos){
vector<int>rev = revers(v);
if(rev[a]>rev[b]&&rev[a]>rev[c]){
curra.push_back(cop(v));
}
else if(rev[b]>rev[a]&&rev[b]>rev[c]){
currb.push_back(cop(v));
}
else{
currc.push_back(cop(v));
}
}
if(max({curra.size(),currb.size(),currc.size()})<=nx){
mov1=max({rec(curra,dep+1),rec(currb,dep+1),rec(currc,dep+1)});
}
//2nd:
curra.clear();
currb.clear();
currc.clear();
for(vector<int>v:pos){
vector<int>rev = revers(v);
if(rev[a]<rev[b]&&rev[a]<rev[c]){
curra.push_back(cop(v));
}
else if(rev[b]<rev[a]&&rev[b]<rev[c]){
currb.push_back(cop(v));
}
else{
currc.push_back(cop(v));
}
}
if(max({curra.size(),currb.size(),currc.size()})<=nx)
mov2=max({rec(curra,dep+1),rec(currb,dep+1),rec(currc,dep+1)});
//3rd:
curra.clear();
currb.clear();
currc.clear();
for(vector<int>v:pos){
vector<int>rev = revers(v);
int mx = max({rev[a],rev[b],rev[c]});
int mn = min({rev[a],rev[b],rev[c]});
if(mx!=rev[a]&&mn!=rev[a]){
curra.push_back(cop(v));
}
else if(mx!=rev[b]&&mn!=rev[b]){
currb.push_back(cop(v));
}
else{
currc.push_back(cop(v));
}
}
if(max({curra.size(),currb.size(),currc.size()})<=nx)
mov3=max({rec(curra,dep+1),rec(currb,dep+1),rec(currc,dep+1)});
//4th:
for(int d = 0;d<mx;d++){
if(a==d||b==d||c==d)
continue;
curra.clear();
currb.clear();
currc.clear();
for(vector<int>v:pos){
vector<int>rev = revers(v);
vector<int>ar = {rev[a],rev[b],rev[c]};
sort(ar.begin(),ar.end());
auto it = lower_bound(ar.begin(),ar.end(),rev[d]);
if(it==ar.end()){
it=ar.begin();
}
if((*it)==rev[a]){
curra.push_back(cop(v));
}
else if((*it)==rev[b]){
currb.push_back(cop(v));
}
else{
currc.push_back(cop(v));
}
}
if(max({curra.size(),currb.size(),currc.size()})<=nx){
mov4=min(mov4,max({rec(curra,dep+1),rec(currb,dep+1),rec(currc,dep+1)}));
if(mov4==max({rec(curra,dep+1),rec(currb,dep+1),rec(currc,dep+1)})){
optd=d;
}
}
}
ans=min({mov1,mov2,mov3,ans,mov4});
if(ans==mov1){
mov[pos]={1,{a,b,c}};
}
else if(ans==mov2){
mov[pos]={2,{a,b,c}};
}
else if(ans==mov3){
mov[pos]={3,{a,b,c}};
}
else if(ans==mov4){
mov[pos]={4,{a,b,c,optd}};
}
}
}
}
return (mp[pos]=ans+1);
}
int fac(int x){
int ans = 1;
for(int i = 1;i<=x;i++){
ans*=i;
}
return ans;
}
void init(int T) {
}
void orderCoins() {
vector<vector<int>>pos(720);
int perm[mx];
iota(perm,perm+mx,0);
for(int i = 0;i<720;i++){
for(int j : perm){
pos[i].push_back(j);
}
next_permutation(perm,perm+mx);
}
int cn = 0;
while(pos.size()>1){
cn++;
rec(pos,cn);
pair<int,vector<int>>curr = mov[pos];
if(curr.first==1){
int a = curr.second[0];
int b = curr.second[1];
int c = curr.second[2];
int h = getHeaviest(a+1,b+1,c+1)-1;
vector<vector<int>>nx;
for(vector<int>v:pos){
vector<int>rev = revers(v);
if(rev[h]>=rev[a]&&rev[h]>=rev[b]&&rev[h]>=rev[c]){
nx.push_back(cop(v));
}
}
pos=nx;
}
else if(curr.first==2){
int a = curr.second[0];
int b = curr.second[1];
int c = curr.second[2];
int h = getLightest(a+1,b+1,c+1)-1;
vector<vector<int>>nx;
for(vector<int>v:pos){
vector<int>rev = revers(v);
if(rev[h]<=rev[a]&&rev[h]<=rev[b]&&rev[h]<=rev[c]){
nx.push_back(cop(v));
}
}
pos=nx;
}
else if(curr.first==3){
vector<vector<int>>nx;
int a = curr.second[0];
int b = curr.second[1];
int c = curr.second[2];
int h = getMedian(a+1,b+1,c+1)-1;
for(vector<int>v:pos){
vector<int>rev = revers(v);
int mx = max({rev[a],rev[b],rev[c]});
int mn = min({rev[a],rev[b],rev[c]});
if(mx!=rev[a]&&mn!=rev[a]){
if(a==h)
nx.push_back(cop(v));
}
else if(mx!=rev[b]&&mn!=rev[b]&&h==b){
if(b==h)
nx.push_back(cop(v));
}
else{
if(c==h)
nx.push_back(cop(v));
}
}
pos=nx;
}
else{
vector<vector<int>>nx;
int a = curr.second[0];
int b = curr.second[1];
int c = curr.second[2];
int d = curr.second[3];
int h = getNextLightest(a+1,b+1,c+1,d+1)-1;
for(vector<int>v:pos){
vector<int>rev = revers(v);
vector<int>ar = {rev[a],rev[b],rev[c]};
sort(ar.begin(),ar.end());
auto it = lower_bound(ar.begin(),ar.end(),rev[d]);
if(it==ar.end()){
it=ar.begin();
}
if((*it)==rev[a]){
if(a==h)
nx.push_back(cop(v));
}
else if((*it)==rev[b]){
if(b==h)
nx.push_back(cop(v));
}
else{
if(c==h)
nx.push_back(cop(v));
}
}
pos=nx;
}
}
assert(pos.size()==1);
int ans[6];
int ind = 0;
for(int i : pos[0]){
ans[ind++]=i+1;
}
answer(ans);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
