Submission #1009852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009852		hotboy2703	Scales (IOI15_scales)	C++14	100 / 100	61 ms	880 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

struct query{
    ll a[4];
    ll type;
};
vector <query> all_query;
ll f(vector <ll> p,query x){
    static ll w[7];
    for (ll i = 0;i < sz(p);i ++)w[p[i]] = i;
    ll cw;
    if (x.type == 0){
        cw = min({w[x.a[0]],w[x.a[1]],w[x.a[2]]});
        for (ll j = 0;j < 3;j ++){
            if (cw == w[x.a[j]])return j;
        }
    }
    if (x.type == 1){
        cw = max({w[x.a[0]],w[x.a[1]],w[x.a[2]]});
        for (ll j = 0;j < 3;j ++){
            if (cw == w[x.a[j]])return j;
        }
    }
    if (x.type == 2){
        cw = w[x.a[0]] + w[x.a[1]] + w[x.a[2]] - min({w[x.a[0]],w[x.a[1]],w[x.a[2]]}) - max({w[x.a[0]],w[x.a[1]],w[x.a[2]]});
    }
    if (x.type == 3){
        cw = 7;
        for (ll j = 0;j < 3;j ++){
            if (w[x.a[j]] > w[x.a[3]] && w[x.a[j]] < cw)cw = w[x.a[j]];
        }
        if (cw == 7)cw = min({w[x.a[0]],w[x.a[1]],w[x.a[2]]});
    }
    for (ll j = 0;j < 3;j ++){
        if (cw == w[x.a[j]])return j;
    }
}
struct node{
    ll c[3];
    query sus;
    vector<vector <ll> > all;
};
vector <node> T;
ll mul3[7];
bool dfs(ll id,ll depth){
    if (sz(T[id].all) > mul3[depth])return 0;
    if (depth==0)return 1;
    for (auto x:all_query){
        vector <vector <ll> > son[3];
        for (auto p:T[id].all){
            son[f(p,x)].push_back(p);
        }
        if (max({sz(son[0]),sz(son[1]),sz(son[2])}) > mul3[depth-1])continue;
        T[id].sus = x;
        bool fail = 0;
        for (ll j = 0;j < 3;j ++){
            T.emplace_back();
            T[id].c[j] = sz(T) - 1;
            T[sz(T)-1].all = son[j];
            if (!dfs(sz(T)-1,depth-1)){
                fail = 1;
                break;
            }
        }
        if (!fail)return 1;
        else{
            T.resize(id+1);
        }
    }
    return 0;
}
void init(int TTT) {
    mul3[0] = 1;
    for (ll i = 1;i <= 6;i ++)mul3[i] = mul3[i-1]*3;
    for (ll i = 1;i <= 6;i ++){
        for (ll j = i + 1;j <= 6;j ++){
            for (ll k = j + 1;k <= 6;k ++){
                for (ll type = 0;type < 3;type++){
                    all_query.push_back({i,j,k,0,type});
                }
                for (ll d = 1;d <= 6;d ++){
                    if (d==i||d==j||d==k)continue;
                    all_query.push_back({i,j,k,d,3});
                }
            }
        }
    }
    T.emplace_back();
    {
        vector <ll> p(6);
        iota(p.begin(),p.end(),1);
        do{
            T[0].all.push_back(p);
        }while (next_permutation(p.begin(),p.end()));
    }
//    cout<<f({2,1,3,4,5,6},{1,2,3,0,0})<<endl;
//    for (auto tmp:all_query){
//        cout<<tmp.type<<' '<<tmp.a[0]<<' '<<tmp.a[1]<<' '<<tmp.a[2]<<' '<<tmp.a[3]<<'\n';
//    }
    assert(dfs(0,6));
//    cout<<T[0].c[0]<<' '<<T[0].c[1]<<' '<<T[0].c[2]<<endl;
    /* ... */
}
void orderCoins() {
    ll cur = 0;
    for (ll i = 6;i >= 1;i --){
        ll res;
        query tmp = T[cur].sus;
//        cout<<tmp.type<<' '<<tmp.a[0]<<' '<<tmp.a[1]<<' '<<tmp.a[2]<<' '<<tmp.a[3]<<'\n';
        if (tmp.type==0)res = getLightest(tmp.a[0],tmp.a[1],tmp.a[2]);
        if (tmp.type==1)res = getHeaviest(tmp.a[0],tmp.a[1],tmp.a[2]);
        if (tmp.type==2)res = getMedian(tmp.a[0],tmp.a[1],tmp.a[2]);
        if (tmp.type==3)res = getNextLightest(tmp.a[0],tmp.a[1],tmp.a[2],tmp.a[3]);
        for (ll j = 0;j < 3;j ++){
            if (res==tmp.a[j]){res=j;break;}
        }
        cur = T[cur].c[res];
    }
    ll W[6];
    for (ll j = 0;j < 6;j++){
        W[j] = T[cur].all[0][j];
    }
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:82:15: warning: unused parameter 'TTT' [-Wunused-parameter]
   82 | void init(int TTT) {
      |           ~~~~^~~
scales.cpp: In function 'll f(std::vector<int>, query)':
scales.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
   47 | }
      | ^
scales.cpp:45:9: warning: 'cw' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |         if (cw == w[x.a[j]])return j;
      |         ^~
scales.cpp: In function 'void orderCoins()':
scales.cpp:125:13: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             if (res==tmp.a[j]){res=j;break;}
      |             ^~

• Subtask 1: 100 / 100