답안 #651000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651000	2022-10-16T10:33:10 Z	MilosMilutinovic	저울 (IOI15_scales)	C++14	100 / 100	31 ms	992 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	852 KB	Output is correct
2	Correct	26 ms	924 KB	Output is correct
3	Correct	26 ms	908 KB	Output is correct
4	Correct	26 ms	888 KB	Output is correct
5	Correct	25 ms	920 KB	Output is correct
6	Correct	26 ms	852 KB	Output is correct
7	Correct	27 ms	848 KB	Output is correct
8	Correct	27 ms	860 KB	Output is correct
9	Correct	26 ms	892 KB	Output is correct
10	Correct	25 ms	876 KB	Output is correct
11	Correct	26 ms	892 KB	Output is correct
12	Correct	26 ms	852 KB	Output is correct
13	Correct	28 ms	928 KB	Output is correct
14	Correct	27 ms	888 KB	Output is correct
15	Correct	27 ms	880 KB	Output is correct
16	Correct	25 ms	852 KB	Output is correct
17	Correct	25 ms	924 KB	Output is correct
18	Correct	25 ms	912 KB	Output is correct
19	Correct	30 ms	876 KB	Output is correct
20	Correct	26 ms	880 KB	Output is correct
21	Correct	27 ms	852 KB	Output is correct
22	Correct	27 ms	884 KB	Output is correct
23	Correct	24 ms	904 KB	Output is correct
24	Correct	25 ms	864 KB	Output is correct
25	Correct	25 ms	852 KB	Output is correct
26	Correct	27 ms	852 KB	Output is correct
27	Correct	25 ms	912 KB	Output is correct
28	Correct	28 ms	852 KB	Output is correct
29	Correct	26 ms	928 KB	Output is correct
30	Correct	24 ms	888 KB	Output is correct
31	Correct	25 ms	980 KB	Output is correct
32	Correct	24 ms	852 KB	Output is correct
33	Correct	28 ms	992 KB	Output is correct
34	Correct	31 ms	852 KB	Output is correct
35	Correct	25 ms	928 KB	Output is correct
36	Correct	25 ms	868 KB	Output is correct
37	Correct	24 ms	940 KB	Output is correct
38	Correct	24 ms	884 KB	Output is correct
39	Correct	26 ms	852 KB	Output is correct
40	Correct	25 ms	852 KB	Output is correct