Submission #1076196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076196		jk_	Scales (IOI15_scales)	C++14	71.43 / 100	7 ms	604 KiB

scales

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

struct permutation {
  array<uint8_t, 6> p;
  permutation(array<uint8_t, 6> array) : p(array) {}
  array<uint8_t, 6> decompress() { return p; }
  //uint16_t order;
  //permutation(array<uint8_t, 6> array) : order(0) {
  //  for (int i = 0; i < 5; ++i)
  //    order |= (uint16_t)((int)array[i] << (3*i));
  //}
  //array<uint8_t, 6> decompress() {
  //  array<uint8_t, 6> ans;
  //  uint8_t last=0^1^2^3^4^5;
  //  for (int i = 0; i < 5; ++i) {
  //    uint8_t x = (order >> (3*i))&0x7;
  //    ans[i] = x;
  //    last ^= x;
  //  }
  //  ans[5] = last;
  //  return ans;
  //}
};

int lightest(array<uint8_t, 6> p, int a, int b, int c) {
  if (p[a] < p[b] && p[a] < p[c]) return 0;
  if (p[b] < p[a] && p[b] < p[c]) return 1;
  if (p[c] < p[a] && p[c] < p[b]) return 2;
  assert(false);
}

int heaviest(array<uint8_t, 6> p, int a, int b, int c) {
  if (p[a] > p[b] && p[a] > p[c]) return 0;
  if (p[b] > p[a] && p[b] > p[c]) return 1;
  if (p[c] > p[a] && p[c] > p[b]) return 2;
  assert(false);
}

int median(array<uint8_t, 6> p, int a, int b, int c) {
  if ((p[a] > p[b] && p[a] < p[c]) ||
      (p[a] < p[b] && p[a] > p[c])) return 0;
  if ((p[b] > p[a] && p[b] < p[c]) ||
      (p[b] < p[a] && p[b] > p[c])) return 1;
  if ((p[c] > p[a] && p[c] < p[b]) ||
      (p[c] < p[a] && p[c] > p[b])) return 2;
  assert(false);
}

int next_lightest(array<uint8_t, 6> p, int a, int b, int c, int d) {
  int ans = -1;
  if (p[a] > p[d]) ans = a;
  if (p[b] > p[d]) if (ans == -1 || p[b] < p[ans]) ans = b;
  if (p[c] > p[d]) if (ans == -1 || p[c] < p[ans]) ans = c;
  if (ans == -1) return lightest(p, a, b, c);
  else return (ans==a ? 0 : (ans==b ? 1 : 2));
}

struct decision {
  vector<permutation> state;
  int question;
  int a, b, c, d;

  array<unique_ptr<decision>, 3> child;

  static unique_ptr<decision> solved(vector<permutation> s) {
    return unique_ptr<decision>(new decision{s, -1, 0,0,0,0, {nullptr, nullptr, nullptr}});
  }

  void interact() {
    if (state.size() == 0) assert(false);
    if (state.size() == 1) {
      auto p = state[0].decompress();
      vector<int> inv(6);
      for (int i = 0; i < 6; ++i)
        inv[p[i]] = i+1;
      answer(inv.data());
      return;
    }
    int ans=0;
    switch (question) {
    case 0: ans = getLightest(a+1, b+1, c+1); break;
    case 1: ans = getHeaviest(a+1, b+1, c+1); break;
    case 2: ans = getMedian(a+1, b+1, c+1); break;
    case 3: ans = getNextLightest(a+1, b+1, c+1, d+1); break;
    default: assert(false);
    }
    if (ans == a+1) child[0]->interact();
    else if (ans == b+1) child[1]->interact();
    else if (ans == c+1) child[2]->interact();
    else assert(false);
  }
};

void print(unique_ptr<decision> const& d, int depth=0) {
  string indent = string(2*depth, ' ');
  cout << indent << "// " << d->state.size() << '\n';
  cout << indent << "  ";
  if (d->state.size() == 0) {
    cout << "assert(false);\n";
    return;
  }
  if (d->state.size() == 1) {
    auto p = d->state[0].decompress();
    cout << "answer(std::array<int, 6>{";
    const char *sep="";
    for (auto x : p) {
      cout << sep << (int)x+1;
      sep = ", ";
    }
    cout << "}.data());\n";
    return;
  }
  array<const char*, 4> function_name{
    "getLightest",
    "getHeaviest",
    "getMedian",
    "getNextLightest",
  };
  cout << "switch (" << function_name[d->question] << '(' << (int)d->a+1 << ", " << (int)d->b+1 << ", " << (int)d->c+1;
  if (d->d != -1)
    cout << ", " << (int)d->d+1;
  cout << ")) {\n";
  for (int i = 0; i < 3; ++i) {
    cout << indent << "  case "<<(i==0?d->a+1:(i==1?d->b+1:d->c+1))<<":\n  ";
    print(d->child[i], depth+1);
    cout << indent << "    break;\n";
  }
  cout << indent << "  default: assert(false);\n";
  cout << indent << "  }\n";
}

int pow3(int e) {
  if (e <= 0) return 1;
  return 3*pow3(e-1);
}

unique_ptr<decision> solve(vector<permutation> state, int max_depth);

template <typename F>
unique_ptr<decision> subsolve(int q, F&& f, vector<permutation> const& state, int max_depth) {
  int max_child_size = pow3(max_depth);
  for (int a = 0; a < 6; ++a) {
    for (int b = a+1; b < 6; ++b) {
      for (int c = b+1; c < 6; ++c) {
        array<vector<permutation>, 3> child;
        array<unique_ptr<decision>, 3> ans;
        for (auto s : state) {
          auto p = s.decompress();
          int r = f(p, a, b, c);
          assert(0 <= r && r < 3);
          child[r].push_back(s);
          if ((int)child[r].size() > max_child_size)
            goto next;
        }
        // cout << "S"<<q << " " <<  max_depth << " " << max_child_size << ' ' << a << ' ' << b << ' ' << c << " | ";
        // for (int i = 0; i < 3; ++i) {
        //   cout << child[i].size() << ' ';
        // }
        // cout << '\n';
        for (int i = 0; i < 3; ++i) {
          ans[i] = solve(child[i], max_depth);
          if (!ans[i]) goto next;
        }

        return unique_ptr<decision>(new decision{state, q, a, b, c, -1, move(ans)});
      next:;
      }
    }
  }
  return nullptr;
}

unique_ptr<decision> subsolve4(int q, vector<permutation> const& state, int max_depth) {
  int max_child_size = pow3(max_depth);
  for (int a = 0; a < 6; ++a) {
    for (int b = a+1; b < 6; ++b) {
      for (int c = b+1; c < 6; ++c) {
        for (int d = 0; d < 6; ++d) {
          if (d==a || d==b || d==c) continue;
          array<vector<permutation>, 3> child;
          array<unique_ptr<decision>, 3> ans{};
          for (auto s : state) {
            auto p = s.decompress();
            int x = next_lightest(p, a, b, c, d);
            child[x].push_back(s);
            if ((int)child[x].size() > max_child_size)
              goto next;
          }
          for (int i = 0; i < 3; ++i) {
            ans[i] = solve(child[i], max_depth);
            if (!ans[i]) goto next;
          }
          // cout << "S"<<4 << " " <<  max_depth << " " << max_child_size << ' ' << a << ' ' << b << ' ' << c << " | ";
          // for (int i = 0; i < 3; ++i) {
          //   cout << child[i].size() << ' ';
          // }
          // cout << '\n';
          return unique_ptr<decision>(new decision{state, q, a, b, c, d, move(ans)});
        next:;
        }
      }
    }
  }
  return nullptr;
}

unique_ptr<decision> solve(vector<permutation> state, int max_depth) {
  if (state.size() <= 1)
    return decision::solved(state);
  if ((int)state.size() > pow3(max_depth)) return nullptr;
  assert(max_depth >= 1);

  if (auto ans = subsolve(0, lightest, state, max_depth-1)) return ans;
  if (auto ans = subsolve(1, heaviest, state, max_depth-1)) return ans;
  if (auto ans = subsolve(2, median, state, max_depth-1)) return ans;
  if (auto ans = subsolve4(3, state, max_depth-1)) return ans;
  return nullptr;
}

unique_ptr<decision> decision_tree;

void init(int) {
  vector<permutation> state;
  array<uint8_t, 6> p = {0,1,2,3,4,5};
  do {
    state.push_back(permutation(p));
    assert(p==permutation(p).decompress());
  } while (next_permutation(p.begin(), p.end()));

  decision_tree = solve(state, 7);
  if (!decision_tree) { cout << "no solution found\n"; }
  assert(decision_tree);

  //print(decision_tree);
}

void orderCoins() {
  decision_tree->interact();
}

• Subtask 1: 71.428571 / 100