Submission #651000

#	Time	Username	Problem	Language	Result	Execution time	Memory
651000		MilosMilutinovic	Scales (IOI15_scales)	C++14	100 / 100	31 ms	992 KiB

scales

/**
 *    author:  wxhtzdy
 *    created: 05.07.2022 11:10:33
**/
#include "scales.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 15000;

int root, ch[N][3], tsz;

struct query {
  int type, a, b, c, d;
  bool operator <(query p) const {
    return type > p.type;
  }
};

vector<query> queries;
query qq[N];

int Solve(query q, vector<int> p) {
  assert((int) p.size() == 6);
  assert(q.a >= 0 && q.a < 6);
  assert(q.b >= 0 && q.b < 6);
  assert(q.c >= 0 && q.c < 6);
  assert(q.d >= 0 && q.d < 6);
  if (q.type == 1) {
    int mn = min({p[q.a], p[q.b], p[q.c]});
    if (p[q.a] == mn) {
      return 0;
    }
    if (p[q.b] == mn) {
      return 1;
    }
    return 2;
  }
  if (q.type == 2) {
    int mx = max({p[q.a], p[q.b], p[q.c]});
    if (p[q.a] == mx) {
      return 0;
    }
    if (p[q.b] == mx) {
      return 1;
    }
    return 2;
  }
  if (q.type == 3) {
    int mn = min({p[q.a], p[q.b], p[q.c]});
    int mx = max({p[q.a], p[q.b], p[q.c]});
    int med = mn ^ mx ^ p[q.a] ^ p[q.b] ^ p[q.c];
    if (p[q.a] == med) {
      return 0;
    }
    if (p[q.b] == med) {
      return 1;
    }
    return 2;
  }
  if (q.type == 4) {
    int idx = -1;
    if (p[q.a] >= p[q.d] && (idx == -1 || p[q.a] < p[idx])) {
      idx = q.a;
    }
    if (p[q.b] >= p[q.d] && (idx == -1 || p[q.b] < p[idx])) {
      idx = q.b;
    }
    if (p[q.c] >= p[q.d] && (idx == -1 || p[q.c] < p[idx])) {
      idx = q.c;
    }
    if (idx == -1) {
      int mn = min({p[q.a], p[q.b], p[q.c]});
      if (p[q.a] == mn) {
        return 0;
      }
      if (p[q.b] == mn) {
        return 1;
      }
      return 2;
    } else {
      if (q.a == idx) {
        return 0;
      }
      if (q.b == idx) {
        return 1;
      }
      return 2;
    }
  }
  assert(false);
}

vector<int> my[N];

mt19937 rng(time(0));

bool build(int& v, vector<vector<int>> p, int dep) {
  if (!v) {
    v = ++tsz;
  }
  if (p.size() <= 1) {
    if (p.size() == 1) {
      my[v] = p[0];
    } else {
      my[v] = vector<int>(6, -1);
    }
    return true;
  }
  if (dep == 6) {
    /*for (auto& perm : p) {
      for (int j : perm) {
        cerr << j + 1 << " ";
      }
      cerr << endl;
    }*/
    return false;
  }
  vector<tuple<int, query, vector<vector<int>>, vector<vector<int>>, vector<vector<int>>>> opt;
  for (auto& q : queries) {
    vector<vector<vector<int>>> go(3);
    for (auto& perm : p) {
      int out = Solve(q, perm);
      assert(0 <= out && out < 3);
      go[out].push_back(perm);
    }
    vector<int> sz(3);
    for (int i = 0; i < 3; i++) {
      sz[i] = go[i].size();
    }
    int d = *max_element(sz.begin(), sz.end()) - *min_element(sz.begin(), sz.end());
    //int d = abs(sz[0] - sz[1]) + abs(sz[0] - sz[2]) + abs(sz[1] - sz[2]);
    if (d <= 1 && build(ch[v][0], go[0], dep + 1) && build(ch[v][1], go[1], dep + 1) && build(ch[v][2], go[2], dep + 1)) {
      qq[v] = q;
      return true;
    }
  }
  return false;
  sort(opt.begin(), opt.end());
  vector<tuple<int, query, vector<vector<int>>, vector<vector<int>>, vector<vector<int>>>> bst;
  for (auto& pp : opt) {
    if (get<0>(pp) == get<0>(opt[0])) {
      bst.push_back(pp);
    }
  }
  /*shuffle(bst.begin(), bst.end(), rng);
  opt = bst;
  qq[v] = get<1>(opt[0]);
  valid = true;
  build(ch[v][0], get<2>(opt[0]), dep + 1);
  build(ch[v][1], get<3>(opt[0]), dep + 1);
  build(ch[v][2], get<4>(opt[0]), dep + 1);
  while (!valid);*/
}

void init(int tt) {
  for (int a = 0; a < 6; a++) {
    for (int b = a + 1; b < 6; b++) {
      for (int c = b + 1; c < 6; c++) {
        queries.push_back({1, a, b, c, 0});
        queries.push_back({2, a, b, c, 0});
        queries.push_back({3, a, b, c, 0});
      }
    }
  }
  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) {
            queries.push_back({4, a, b, c, d});
          }
        }
      }
    }
  }
  vector<vector<int>> p;
  vector<int> perm(6);
  iota(perm.begin(), perm.end(), 0);
  do {
    p.push_back(perm);
  } while (next_permutation(perm.begin(), perm.end()));
//  cerr << "building" << endl;
  build(root, p, 0);
//  cerr << endl;
//  cerr << qq[root].type << " " << qq[root].a << " " << qq[root].b << " " << qq[root].c << endl;
}


int Idx(int a, int b, int c, int d) {
  if (a == d) return 0;
  if (b == d) return 1;
  if (c == d) return 2;
  assert(false);
}

int cc = 0;

int Ask(query q) {
  cc += 1;
  if (q.type == 1) {
    return Idx(q.a, q.b, q.c, getLightest(q.a + 1, q.b + 1, q.c + 1) - 1);
  }
  if (q.type == 2) {
    return Idx(q.a, q.b, q.c, getHeaviest(q.a + 1, q.b + 1, q.c + 1) - 1);
  }
  if (q.type == 3) {
    return Idx(q.a, q.b, q.c, getMedian(q.a + 1, q.b + 1, q.c + 1) - 1);
  }
  if (q.type == 4) {
    return Idx(q.a, q.b, q.c, getNextLightest(q.a + 1, q.b + 1, q.c + 1, q.d + 1) - 1);
  }
  assert(false);
}

vector<int> ans;

void dfs(int v) {
  if (!my[v].empty()) {
    ans = my[v];
    return;
  }
  if (v == 0) {
    return;
  }
//  cerr << qq[v].type << " " << qq[v].a << " " << qq[v].b << " " << qq[v].c << endl;
  int nxt = Ask(qq[v]);
//  cerr << "nxt = " << nxt << endl;
  dfs(ch[v][nxt]);
}


void orderCoins() {
//  cerr << "answering" << endl;
  ans = vector<int>(6, -1);
  cc = 0;
  dfs(root);
  assert(ans[0] != -1);
  //assert(cc <= 6);
  int res[6];
  for (int i = 0; i < 6; i++) {
    res[ans[i]] = i + 1;
  }
  answer(res);
}

Compilation message (stderr)

scales.cpp: In function 'bool build(int&, std::vector<std::vector<int> >, int)':
scales.cpp:130:25: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
  130 |       sz[i] = go[i].size();
      |               ~~~~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:157:15: warning: unused parameter 'tt' [-Wunused-parameter]
  157 | void init(int tt) {
      |           ~~~~^~

• Subtask 1: 100 / 100