Submission #432816

#	Time	Username	Problem	Language	Result	Execution time	Memory
432816		jeroenodb	Scales (IOI15_scales)	C++14	100 / 100	41 ms	588 KiB

scales

#ifndef GRADER
#include "scales.h"
#endif
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
typedef array<char,6> state;
vector<state> getcombs() {
    vector<state> res;
    for(int i=0;i<1<<6;++i) {
        vector<int8_t> h, o;
        for(int8_t j=0;j<6;++j) {
            if((1<<j)&i)
                h.push_back(j);
            else o.push_back(j);
        }
        if(h.size()==3) res.push_back(state{h[0],h[1],h[2], o[0],o[1],o[2]});
    }
    return res;
}
const vector<state> combs = getcombs();
const int allowed[] = {1,3,9,27,81,243};
struct maybe{
    vector<state> to[3];
    bool good=true;
    maybe(int8_t op, vector<state>& left, state comb, uint8_t dead=100) {
        for(auto s : left) {
            array<int8_t, 3> v = {s[comb[0]],s[comb[1]],s[comb[2]]};
            sort(all(v));
            if(op==0) {
                for(int i=0;i<3;++i) if(s[comb[i]]==v[2]) to[i].push_back(s);
            } else if(op==1) {
                for(int i=0;i<3;++i) if(s[comb[i]]==v[0]) to[i].push_back(s);
            } else if(op==2) {
                for(int i=0;i<3;++i) if(s[comb[i]]==v[1]) to[i].push_back(s);
            } else {
                int8_t d = s[comb[op]];
                int8_t want=v[0];
                for(auto i: v) {
                    if(i>d) {
                        want=i;
                        break;
                    }
                }
                for(int i=0;i<3;++i) if(s[comb[i]]==want) to[i].push_back(s);
            }
        }
        for(int i=0;i<3;++i) if(dead<100 and to[i].size()>allowed[dead-1]) {
            good = false;
        }
    }
};
struct res {
    bool good;
    int8_t op, comb;
};
map<vector<state>,res> dp;

res solve(vector<state>& left, int d = 6) {
    if(left.size()<=1) return {true,{}};
    auto it = dp.find(left);
    if(it!=dp.end()) return it->second;
    // try each operation
    for(int8_t i=0;i<combs.size();++i) {
        // try each op
        for(int8_t op=0;op<6;++op) {
            maybe m(op,left,combs[i],d);
            if(m.good) {
                for(int i=0;i<3;++i) {
                    auto r = solve(m.to[i],d-1);
                    if(!r.good) {
                        m.good=false;
                        break;
                    }
                }
                if(m.good) {
                    return dp[left] = {true,op,i};
                }
            }
        }
    }
    return dp[left] = {false,-1,-1};
}
vector<state> allperms() {
    state s;
    iota(all(s),0);
    vector<state> complete;
    do {
        complete.push_back(s);
    } while(next_permutation(all(s)));
    return complete;
}
void init(int T) {
}

void orderCoins() {
    auto s = allperms();
    while(s.size()>1) {
        auto ans = solve(s);
        assert(ans.good);
        auto myc = combs[ans.comb];
        auto partition = maybe(ans.op,s,myc);
        int q;
        int A=myc[0]+1,B=myc[1]+1,C=myc[2]+1,D=myc[ans.op]+1;
        if(ans.op==0) {
            q=getHeaviest(A,B,C);
        } else if(ans.op==1) {
            q=getLightest(A,B,C);
        } else if(ans.op==2) {
            q=getMedian(A,B,C);
        } else {
            q=getNextLightest(A,B,C,D);
        }
        q--;
        for(int i=0;i<3;++i) {
            if(myc[i]==q) {
                s= partition.to[i];
                break;
            }
        }
    }
    int order[6];
    for(int i=0;i<6;++i) {
        order[s[0][i]]=i+1;
    }
    answer(order);
}

Compilation message (stderr)

scales.cpp: In constructor 'maybe::maybe(int8_t, std::vector<std::array<char, 6> >&, state, uint8_t)':
scales.cpp:56:58: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<char, 6> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   56 |         for(int i=0;i<3;++i) if(dead<100 and to[i].size()>allowed[dead-1]) {
      |                                              ~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp: In function 'res solve(std::vector<std::array<char, 6> >&, int)':
scales.cpp:68:39: warning: missing initializer for member 'res::comb' [-Wmissing-field-initializers]
   68 |     if(left.size()<=1) return {true,{}};
      |                                       ^
scales.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int8_t' {aka 'signed char'} and 'std::vector<std::array<char, 6> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int8_t i=0;i<combs.size();++i) {
      |                    ~^~~~~~~~~~~~~
scales.cpp:75:38: warning: conversion from 'int' to 'uint8_t' {aka 'unsigned char'} may change value [-Wconversion]
   75 |             maybe m(op,left,combs[i],d);
      |                                      ^
scales.cpp:77:25: warning: declaration of 'i' shadows a previous local [-Wshadow]
   77 |                 for(int i=0;i<3;++i) {
      |                         ^
scales.cpp:72:16: note: shadowed declaration is here
   72 |     for(int8_t i=0;i<combs.size();++i) {
      |                ^
scales.cpp: In function 'void init(int)':
scales.cpp:101:15: warning: unused parameter 'T' [-Wunused-parameter]
  101 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:132:22: warning: array subscript has type 'char' [-Wchar-subscripts]
  132 |         order[s[0][i]]=i+1;
      |                      ^

• Subtask 1: 100 / 100