Submission #588673

#	Time	Username	Problem	Language	Result	Execution time	Memory
588673		lorenzoferrari	Scales (IOI15_scales)	C++17	71.43 / 100	71 ms	344 KiB

scales

/*
for implementation's sake, I'd like to compare p[a],p[b],p[c], not a,b,c
  -> mess around with the inverse of a permutation (?)
*/

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

#define sz size

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]; }
};

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;
}

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 < 4; ++i) {
    if (ans-1 == o[i]) {
      // cerr << ans << "\n";
      cur = s[i];
      break;
    }
  }
}

int T;
vector<perm> perms;

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()));
}

void orderCoins() {
  vector<perm> cur = perms;
  while (cur.size() != 1) {
    // cerr << "cur.size(): " << cur.size() << endl;
    int best_worst_case = 1e9;
    op best_op;
    for (int a = 0; a < 6; ++a) for (int b = a+1; b < 6; ++b) for (int c = b+1; c < 6; ++c) {
      op o0(0, {a, b, c});
      op o1(1, {a, b, c});
      op o2(2, {a, b, c});
      auto s0 = simulate(cur, o0);
      auto s1 = simulate(cur, o1);
      auto s2 = simulate(cur, o2);
      if (int(max({s0[0].sz(), s0[1].sz(), s0[2].sz()})) < best_worst_case) {
        best_op = o0;
        best_worst_case = int(max({s0[0].sz(), s0[1].sz(), s0[2].sz()}));
      }
      if (int(max({s1[0].sz(), s1[1].sz(), s1[2].sz()})) < best_worst_case) {
        best_op = o1;
        best_worst_case = int(max({s1[0].sz(), s1[1].sz(), s1[2].sz()}));
      }
      if (int(max({s2[0].sz(), s2[1].sz(), s2[2].sz()})) < best_worst_case) {
        best_op = o2;
        best_worst_case = int(max({s2[0].sz(), s2[1].sz(), s2[2].sz()}));
      }
      for (int d = 0; d < 6; ++d) {
        if (d == a || d == b || d == c) continue;
        op o3(3, {a, b, c, d});
        auto s3 = simulate(cur, o3);
        if (int(max({s3[0].sz(), s3[1].sz(), s3[2].sz()})) < best_worst_case) {
          best_op = o3;
          best_worst_case = int(max({s3[0].sz(), s3[1].sz(), s3[2].sz()}));
        }
      }
    }
    actually_ask(cur, best_op);
  }
  int w[6];
  for (int i = 0; i < 6; ++i) {
    // w[i] = int(cur[0][i]) + 1;
    w[cur[0][i]] = i+1;
    // actually, w[cur[0][i]] = i+1 or smth
  }
  answer(w);
}

Compilation message (stderr)

scales.cpp: In constructor 'op::op(int8_t, std::array<int, 4>)':
scales.cpp:19: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]
   19 |     args[0] = a[0];
      |                  ^
scales.cpp:20: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]
   20 |     args[1] = a[1];
      |                  ^
scales.cpp:21: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]
   21 |     args[2] = a[2];
      |                  ^
scales.cpp:22: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]
   22 |     args[3] = a[3];
      |                  ^
scales.cpp: In constructor 'query::query(const op&, int8_t)':
scales.cpp:32:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   32 |   query(const op& o, const int8_t a) : o(o), ans(a) {}
      |         ~~~~~~~~~~^
scales.cpp:29:6: note: shadowed declaration is here
   29 |   op o;
      |      ^
scales.cpp: In constructor 'query::query(const op&, int8_t)':
scales.cpp:32:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   32 |   query(const op& o, const int8_t a) : o(o), ans(a) {}
      |         ~~~~~~~~~~^
scales.cpp:29:6: note: shadowed declaration is here
   29 |   op o;
      |      ^
scales.cpp: In constructor 'query::query(const op&, int8_t)':
scales.cpp:32:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   32 |   query(const op& o, const int8_t a) : o(o), ans(a) {}
      |         ~~~~~~~~~~^
scales.cpp:29:6: note: shadowed declaration is here
   29 |   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:65:29: warning: conversion from 'int' to 'int8_t' {aka 'signed char'} may change value [-Wconversion]
   65 |       if (works(p, query(o, i))) ans[i].push_back(p);
      |                             ^
scales.cpp: In function 'void init(int)':
scales.cpp:106:15: warning: declaration of 'T' shadows a global declaration [-Wshadow]
  106 | void init(int T) {
      |           ~~~~^
scales.cpp:103:5: note: shadowed declaration is here
  103 | int T;
      |     ^

• Subtask 1: 71.428571 / 100