#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int mx = 6;
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;
}
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++;
int req = (int)pow(3,mx-cn);
pair<int,vector<int>>curr;
int z = 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(z<=req)
break;
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()})<z){
curr={1,{a,b,c}};
z=max({curra.size(),currb.size(),currc.size()});
}
//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()})<z){
curr={2,{a,b,c}};
z=max({curra.size(),currb.size(),currc.size()});
}
//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()})<z){
curr={3,{a,b,c}};
z=max({curra.size(),currb.size(),currc.size()});
}
//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()})<z){
curr={4,{a,b,c,d}};
z=max({curra.size(),currb.size(),currc.size()});
}
}
}
}
}
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... |
