Submission #1032755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032755		socpite	Scales (IOI15_scales)	C++17	100 / 100	101 ms	2588 KiB

scales

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

const int N = 6;

typedef array<int, N> perm;
typedef array<int, 5> operation; // type, argv[0], argv[1], argv[2], argv[3];

map<vector<perm>, operation> mp;

int chk(perm &P, operation &O){
    sort(O.begin()+1, O.begin()+4, [&](int a, int b){return P[a] < P[b];});
    if(O[0] <= 2)return O[O[0] + 1];
    else {
        if(P[O[4]] < P[O[1]] || P[O[4]] > P[O[3]])return O[1];
        else if(P[O[4]] < P[O[2]])return O[2];
        return O[3];
    }
}

bool dfs(vector<perm> vec, int lim = 729){
    // cout << vec.size() << " " << lim << endl;
    if(vec.size() > lim)return false;
    if(mp.find(vec) != mp.end() || vec.size() <= 1)return true;

    for(int ty = 0; ty < 3; ty++){
        for(int i = 0; i < N; i++){
            for(int j = i+1; j < N; j++){
                for(int k = j + 1; k < N; k++){
                    operation O({ty, i, j, k, -1});
                    vector<perm> nw[3];
                    for(auto &v: vec){
                        int ans = chk(v, O);
                        if(ans == i)nw[0].push_back(v);
                        else if(ans == j)nw[1].push_back(v);
                        else nw[2].push_back(v);
                    }
                    if(dfs(nw[0], lim/3) && dfs(nw[1], lim/3) && dfs(nw[2], lim/3)){
                        mp[vec] = O;
                        return true;
                    }
                }
            }
        }
    }
    for(int d = 0; d < N; d++){
        for(int i = 0; i < N; i++){
            if(i == d)continue;
            for(int j = i+1; j < N; j++){
                if(j == d)continue;
                for(int k = j+1; k < N; k++){
                    if(k == d)continue;
                    operation O({3, i, j, k, d});
                    vector<perm> nw[3];
                    for(auto &v: vec){
                        int ans = chk(v, O);
                        if(ans == i)nw[0].push_back(v);
                        else if(ans == j)nw[1].push_back(v);
                        else nw[2].push_back(v);
                    }
                    if(dfs(nw[0], lim/3) && dfs(nw[1], lim/3) && dfs(nw[2], lim/3)){
                        mp[vec] = O;
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

vector<perm> allperm;
void init(int T) {
    perm P;
    iota(P.begin(), P.end(), 0);
    while(true){
        allperm.push_back(P);
        if(!next_permutation(P.begin(), P.end()))break;
    }
    dfs(allperm);
}

int call_operation(operation O){
    for(int i = 1; i < 5; i++)O[i]++;
    // for(auto v: O)cout << v << " ";
    // cout << endl;
    int re;
    if(O[0] == 0)re = getLightest(O[1], O[2], O[3]);
    if(O[0] == 1)re = getMedian(O[1], O[2], O[3]);
    if(O[0] == 2)re = getHeaviest(O[1], O[2], O[3]);
    if(O[0] == 3)re = getNextLightest(O[1], O[2], O[3], O[4]);
    return re-1;
}

perm solve(vector<perm> vec){
    if(vec.size() == 1)return vec[0];
    operation O = mp[vec];
    int re = call_operation(O);
    vector<perm> nw;
    for(auto &v: vec){
        if(chk(v, O) == re)nw.push_back(v);
    }
    return solve(nw);
}

void orderCoins() {
    /* ... */
    int W[] = {1, 2, 3, 4, 5, 6};
    perm P = solve(allperm);
    for(int i = 0; i < 6; i++){
        W[P[i]] = i+1;
    }
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'bool dfs(std::vector<std::array<int, 6> >, int)':
scales.cpp:24:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 6> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     if(vec.size() > lim)return false;
      |        ~~~~~~~~~~~^~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:74:15: warning: unused parameter 'T' [-Wunused-parameter]
   74 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int call_operation(operation)':
scales.cpp:93:15: warning: 're' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |     return re-1;
      |               ^

• Subtask 1: 100 / 100