Submission #1261209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261209		kl0989e	Scales (IOI15_scales)	C++20	100 / 100	17 ms	648 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

map<pair<vector<vi>,int>,vi> getq;

vi mx={243,81,27,9,3,1};

bool search(vector<vi>& anses, int de=0) {
    if (getq.count({anses,de}) || anses.size()<=1) {
        return 1;
    }
    for (int cn=1; cn<=3; cn++) {
        for (int a=1; a<=6; a++) {
            for (int b=a+1; b<=6; b++) {
                for (int c=b+1; c<=6; c++) {
                    vector<vi> aa,bb,cc;
                    for (auto t:anses) {
                        int cnt=0;
                        for (int i=0; i<6; i++) {
                            if (t[i]==a) {
                                cnt++;
                                if (cnt==cn) {
                                    aa.pb(t);
                                    break;
                                }
                            }
                            else if (t[i]==b) {
                                cnt++;
                                if (cnt==cn) {
                                    bb.pb(t);
                                    break;
                                }
                            }
                            else if (t[i]==c) {
                                cnt++;
                                if (cnt==cn) {
                                    cc.pb(t);
                                    break;
                                }
                            }
                        }
                    }
                    if (max(aa.size(),max(bb.size(),cc.size()))<=mx[de]) {
                        getq[{anses,de}]={cn,a,b,c};
                        if (search(aa,de+1) && search(bb,de+1) && search(cc,de+1)) {
                            return 1;
                        }
                    }
                }
            }
        }
    }
    for (int a=1; a<=6; a++) {
        for (int b=a+1; b<=6; b++) {
            for (int c=b+1; c<=6; c++) {
                for (int d=c+1; d<=6; d++) {
                    vector<vi> aa,bb,cc;
                    for (auto t:anses) {
                        bool act=0;
                        for (int i=0; ; i=(i+1)%6) {
                            if (t[i]==d) {
                                act=1;
                            }
                            else if (t[i]==a && act) {
                                aa.pb(t);
                                break;
                            }
                            else if (t[i]==b && act) {
                                bb.pb(t);
                                break;
                            }
                            else if (t[i]==c && act) {
                                cc.pb(t);
                                break;
                            }
                        }
                    }
                    if (max(aa.size(),max(bb.size(),cc.size()))<=mx[de]) {
                        getq[{anses,de}]={4,a,b,c,d};
                        if (search(aa,de+1) && search(bb,de+1) && search(cc,de+1)) {
                            return 1;
                        }
                    }
                }
            }
        }
    }
    getq.erase({anses,de});
    return 0;
}

void init(int _) {
    vector<vi> anses(720);
    vi t={1,2,3,4,5,6};
    for (int i=0; i<720; i++) {
        anses[i]=t;
        next_permutation(all(t));
    }
    assert(search(anses));
}

void orderCoins() {
    vector<vi> anses(720);
    vi t={1,2,3,4,5,6};
    for (int i=0; i<720; i++) {
        anses[i]=t;
        next_permutation(all(t));
    }
    int i=0;
    while (anses.size()>1) {
        vi q=getq[{anses,i++}];
        if (q[0]!=4) {
            int resp;
            int cn=q[0],a=q[1],b=q[2],c=q[3];
            if (cn==1) {
                resp=getLightest(a,b,c);
            }
            else if (cn==2) {
                resp=getMedian(a,b,c);
            }
            else {
                resp=getHeaviest(a,b,c);
            }
            vector<vi> newanses;
            for (auto t:anses) {
                int cnt=0;
                for (int i=0; i<6; i++) {
                    if (t[i]==a) {
                        cnt++;
                        if (cnt==cn) {
                            if (resp==a) {
                                newanses.pb(t);
                            }
                            break;
                        }
                    }
                    else if (t[i]==b) {
                        cnt++;
                        if (cnt==cn) {
                            if (resp==b) {
                                newanses.pb(t);
                            }
                            break;
                        }
                    }
                    else if (t[i]==c) {
                        cnt++;
                        if (cnt==cn) {
                            if (resp==c) {
                                newanses.pb(t);
                            }
                            break;
                        }
                    }
                }
            }
            swap(anses,newanses);
        }
        else {
            int a=q[1],b=q[2],c=q[3],d=q[4];
            int resp=getNextLightest(a,b,c,d);
            vector<vi> newanses;
            for (auto t:anses) {
                bool act=0;
                for (int i=0; ; i=(i+1)%6) {
                    if (t[i]==d) {
                        act=1;
                    }
                    else if (t[i]==a && act) {
                        if (resp==a) {
                            newanses.pb(t);
                        }
                        break;
                    }
                    else if (t[i]==b && act) {
                        if (resp==b) {
                            newanses.pb(t);
                        }
                        break;
                    }
                    else if (t[i]==c && act) {
                        if (resp==c) {
                            newanses.pb(t);
                        }
                        break;
                    }
                }
            }
            swap(anses,newanses);
        }
    }
    int ans[6];
    for (int i=0; i<6; i++) {
        ans[i]=anses[0][i];
    }
    answer(ans);
}

• Subtask 1: 100 / 100