Submission #917615

#	Time	Username	Problem	Language	Result	Execution time	Memory
917615		nguyentunglam	Scales (IOI15_scales)	C++17	73.21 / 100	573 ms	760 KiB

scales

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

mt19937 rng(1);

int n = 6;
const int T = 2;

int order[10];

vector<tuple<int, int, int> > three;
vector<tuple<int, int, int, int> > four;

void init(int T) {
  for(int a = 1; a <= n; a++) for(int b = a + 1; b <= n; b++) for(int c = b + 1; c <= n; c++) {
    three.emplace_back(a, b, c);
  }
  for(int d = 1; d <= n; d++) for(int a = 1; a <= n; a++) for(int b = a + 1; b <= n; b++) for(int c = b + 1; c <= n; c++) {
    if (d != a && d != b && d != c) {
      four.emplace_back(a, b, c, d);
    }
  }
}

int ask_three(int a, int b, int c, int type, vector<int> tmp) {
  order[1] = a; order[2] = b; order[3] = c;
  sort(order + 1, order + 4, [&] (const int &x, const int &y) {
       return tmp[x] < tmp[y];
       });
  return order[type];
}

int ask_four(int a, int b, int c, int d, vector<int> tmp) {
  int ret = 0;
  tmp[0] = 1e9;
  if (tmp[a] > tmp[d] && tmp[a] < tmp[ret]) ret = a;
  if (tmp[b] > tmp[d] && tmp[b] < tmp[ret]) ret = b;
  if (tmp[c] > tmp[d] && tmp[c] < tmp[ret]) ret = c;
  if (ret == 0) return ask_three(a, b, c, 1, tmp);
  return ret;
}

void orderCoins() {
  shuffle(three.begin(), three.end(), rng);
  shuffle(four.begin(), four.end(), rng);
  vector<vector<int> > p;

  for(int i = 1; i <= n; i++) order[i] = i;

  do {
    vector<int> tmp(n + 1);
    for(int i = 1; i <= n; i++) tmp[i] = order[i];
    p.push_back(tmp);
  } while (next_permutation(order + 1, order + n + 1));

  while (p.size() > 1) {
    pair<int, int> best = make_pair(1e9, 1e9);
    int _a, _b, _c, _d, _t;

    for(auto &[a, b, c, d] : four) {
      int worst1 = 0, worst2 = 0;
      for(int result = 1; result <= n; result++) {
        int sat = 0;
        for(auto &tmp : p) sat += result == ask_four(a, b, c, d, tmp);
        if (sat) {
          worst2 = max(worst2, sat);
          if (worst1 < worst2) swap(worst1, worst2);
        }
      }
      worst1 /= T; worst2 /= T;
      if (!worst1 || worst1 == p.size()) continue;
      if (best > make_pair(worst1, worst2)) {
        best = make_pair(worst1, worst2);
        _a = a;
        _b = b;
        _c = c;
        _d = d;
        _t = 0;
      }
    }

    for(auto &[a, b, c] : three) for(int type = 3; type >= 1; type--) {
      int worst1 = 0, worst2 = 0;
      for(int result = 1; result <= n; result++) {
        int sat = 0;
        for(auto &tmp : p) sat += result == ask_three(a, b, c, type, tmp);
        if (sat) {
          worst2 = max(worst2, sat);
          if (worst1 < worst2) swap(worst1, worst2);
        }
      }
      if (!worst1 || worst1 == p.size()) continue;
      worst1 /= T; worst2 /= T;
      if (best > make_pair(worst1, worst2)) {
        best = make_pair(worst1, worst2);
        _a = a;
        _b = b;
        _c = c;
        _t = type;
      }
    }

    #ifdef ngu
    cout << _a << " " << _b << " " << _c << " " << _d << " " << _t << endl;
    #endif // ngu

    int result = 0;
    vector<vector<int> > _p;
    if (_t) {
      if (_t == 1) result = getLightest(_a, _b, _c);
      if (_t == 2) result = getMedian(_a, _b, _c);
      if (_t == 3) result = getHeaviest(_a, _b, _c);
      for(auto &tmp : p) if (ask_three(_a, _b, _c, _t, tmp) == result) {
        _p.push_back(tmp);
      }
      assert(_p.size() < p.size());
      p = _p;
    }

    else {
      result = getNextLightest(_a, _b, _c, _d);
      for(auto &tmp : p) if (ask_four(_a, _b, _c, _d, tmp) == result) {
        _p.push_back(tmp);
      }
      assert(_p.size() < p.size());
      p = _p;
    }
  }

  vector<int> tmp = p.back();
  int hidden[n];
  for(int i = 1; i <= n; i++) hidden[tmp[i] - 1] = i;
  #ifdef ngu
  for(int i = 0; i < n; i++) cerr << hidden[i] << " ";
  #endif // ngu

  answer(hidden);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:15:15: warning: declaration of 'T' shadows a global declaration [-Wshadow]
   15 | void init(int T) {
      |           ~~~~^
scales.cpp:8:11: note: shadowed declaration is here
    8 | const int T = 2;
      |           ^
scales.cpp:15:15: warning: unused parameter 'T' [-Wunused-parameter]
   15 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:72:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |       if (!worst1 || worst1 == p.size()) continue;
      |                      ~~~~~~~^~~~~~~~~~~
scales.cpp:93:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |       if (!worst1 || worst1 == p.size()) continue;
      |                      ~~~~~~~^~~~~~~~~~~
scales.cpp:111:7: warning: '_t' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |       if (_t == 1) result = getLightest(_a, _b, _c);
      |       ^~
scales.cpp:122:31: warning: '_d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |       result = getNextLightest(_a, _b, _c, _d);
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp:122:31: warning: '_c' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:122:31: warning: '_b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:122:31: warning: '_a' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 73.214286 / 100