Submission #590934

#	Time	Username	Problem	Language	Result	Execution time	Memory
590934		lorenzoferrari	Scales (IOI15_scales)	C++17	71.43 / 100	105 ms	336 KiB

scales

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

using perm = array<int8_t, 6>;

struct op {
  int8_t type;
  array<int8_t, 4> args;
  op() : type(-1) {}
  op(int8_t w, array<int, 4> a) : type(w) {
    args[0] = a[0];
    args[1] = a[1];
    args[2] = a[2];
    args[3] = a[3];
  }
  int8_t get_type() const { return type; }
  int8_t operator[](const int i) const { return args[i]; }
};
ostream& operator<<(ostream& os, const op& o) {
  os << "(" << int(o.type) << ", {" << int(o[0]) << "," << int(o[1]) << "," << int(o[2]);
  if (o.type == 3) os << "," << int(o[3]);
  os << "})";
  return os;
}

struct query {
  op o;
  int8_t ans;
  query() : ans(-1) {}
  query(const op& o, const int8_t a) : o(o), ans(a) {}
  int8_t type() const { return o.get_type(); }
  int8_t operator[](const int i) const { return o[i]; }
};

bool works(const perm& p, const query& q) {
  if (q.type() != 3) {
    int cnt = 0;
    for (int i = 0; i < 3; ++i) {
      cnt += (p[q[i]] > p[q[q.ans]]);
    }
    return cnt == q.type();
  } else {
    int cnt = 0;
    for (int i = 0; i < 3; ++i) cnt += (p[q[i]] > p[q[3]]);
    int tans = -1;
    if (cnt == 0) {
      if (p[q[0]] < p[q[tans]] || tans == -1) tans = 0;
      if (p[q[1]] < p[q[tans]] || tans == -1) tans = 1;
      if (p[q[2]] < p[q[tans]] || tans == -1) tans = 2;
    } else {
      if (p[q[0]] > p[q[3]] && (tans == -1 || p[q[0]] < p[q[tans]])) tans = 0;
      if (p[q[1]] > p[q[3]] && (tans == -1 || p[q[1]] < p[q[tans]])) tans = 1;
      if (p[q[2]] > p[q[3]] && (tans == -1 || p[q[2]] < p[q[tans]])) tans = 2;
    }
    return q.ans == tans;
  }
}

array<vector<perm>, 3> simulate(const vector<perm>& cur, const op& o) {
  array<vector<perm>, 3> ans;
  for (const perm& p : cur) {
    for (int i = 0; i < 3; ++i) {
      if (works(p, query(o, i))) ans[i].push_back(p);
    }
  }
  return ans;
}

int worst_case(const vector<perm>& cur, const op& o) {
  auto s = simulate(cur, o);
  return int(max(max(s[0].size(), s[1].size()), s[2].size()));
}

void answer(int w[]);
int getHeaviest(int A, int B, int C); // type 0
int getMedian(int A, int B, int C);   // type 1
int getLightest(int A, int B, int C); // type 2
int getNextLightest(int A, int B, int C, int D); // type 3

void actually_ask(vector<perm>& cur, const op& o) {
  auto s = simulate(cur, o);
  int ans = -1;
  switch (o.type) {
    case 0:
      ans = getHeaviest(o[0]+1, o[1]+1, o[2]+1);
      break;
    case 1:
      ans = getMedian(o[0]+1, o[1]+1, o[2]+1);
      break;
    case 2:
      ans = getLightest(o[0]+1, o[1]+1, o[2]+1);
      break;
    case 3:
      ans = getNextLightest(o[0]+1, o[1]+1, o[2]+1, o[3]+1);
      break;
  }
  for (int i = 0; i < 3; ++i) {
    if (ans-1 == o[i]) {
      cur = s[i];
      break;
    }
  }
}

int T;
vector<perm> perms;
vector<op> ops;

void init(int T) {
  ::T = T;
  perms.reserve(720);
  perm p{0,1,2,3,4,5};
  do {
    perms.push_back(p);
  } while (next_permutation(p.begin(), p.end()));
  for (int a = 0; a < 6; ++a) for (int b = a+1; b < 6; ++b) for (int c = b+1; c < 6; ++c) {
    ops.push_back(op(0, {a,b,c}));
    ops.push_back(op(1, {a,b,c}));
    ops.push_back(op(2, {a,b,c}));
    for (int d = 0; d < 6; ++d) {
      if (d == a || d == b || d == c) continue;
      ops.push_back(op(3, {a, b, c, d}));
    }
  }
}

void orderCoins() {
  vector<perm> cur = perms;
  while (cur.size() != 1) {
    int best = 720;
    op o(-1,{-1,-1,-1,-1});
    for (const op& x : ops) {
      if (worst_case(cur, x) <= best) {
        best = worst_case(cur, x);
        o = x;
      }
    }
    actually_ask(cur, o);
  }
  int w[6];
  for (int i = 0; i < 6; ++i) {
    w[cur[0][i]] = i+1;
  }
  answer(w);
}

Compilation message (stderr)

scales.cpp: In constructor 'op::op(int8_t, std::array<int, 4>)':
scales.cpp:12:18: warning: conversion from 'std::array<int, 4>::value_type' {aka 'int'} to 'std::array<signed char, 4>::value_type' {aka 'signed char'} may change value [-Wconversion]
   12 |     args[0] = a[0];
      |                  ^
scales.cpp:13:18: warning: conversion from 'std::array<int, 4>::value_type' {aka 'int'} to 'std::array<signed char, 4>::value_type' {aka 'signed char'} may change value [-Wconversion]
   13 |     args[1] = a[1];
      |                  ^
scales.cpp:14:18: warning: conversion from 'std::array<int, 4>::value_type' {aka 'int'} to 'std::array<signed char, 4>::value_type' {aka 'signed char'} may change value [-Wconversion]
   14 |     args[2] = a[2];
      |                  ^
scales.cpp:15:18: warning: conversion from 'std::array<int, 4>::value_type' {aka 'int'} to 'std::array<signed char, 4>::value_type' {aka 'signed char'} may change value [-Wconversion]
   15 |     args[3] = a[3];
      |                  ^
scales.cpp: In constructor 'query::query(const op&, int8_t)':
scales.cpp:31:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   31 |   query(const op& o, const int8_t a) : o(o), ans(a) {}
      |         ~~~~~~~~~~^
scales.cpp:28:6: note: shadowed declaration is here
   28 |   op o;
      |      ^
scales.cpp: In constructor 'query::query(const op&, int8_t)':
scales.cpp:31:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   31 |   query(const op& o, const int8_t a) : o(o), ans(a) {}
      |         ~~~~~~~~~~^
scales.cpp:28:6: note: shadowed declaration is here
   28 |   op o;
      |      ^
scales.cpp: In constructor 'query::query(const op&, int8_t)':
scales.cpp:31:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   31 |   query(const op& o, const int8_t a) : o(o), ans(a) {}
      |         ~~~~~~~~~~^
scales.cpp:28:6: note: shadowed declaration is here
   28 |   op o;
      |      ^
scales.cpp: In function 'std::array<std::vector<std::array<signed char, 6> >, 3> simulate(const std::vector<std::array<signed char, 6> >&, const op&)':
scales.cpp:64:29: warning: conversion from 'int' to 'int8_t' {aka 'signed char'} may change value [-Wconversion]
   64 |       if (works(p, query(o, i))) ans[i].push_back(p);
      |                             ^
scales.cpp: In function 'void init(int)':
scales.cpp:110:15: warning: declaration of 'T' shadows a global declaration [-Wshadow]
  110 | void init(int T) {
      |           ~~~~^
scales.cpp:106:5: note: shadowed declaration is here
  106 | int T;
      |     ^

• Subtask 1: 71.428571 / 100