oj.uz

답안 #590939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590939 2022-07-06T15:06:43 Z lorenzoferrari 저울 (IOI15_scales) C++17
72.0238 / 100
 94 ms 460 KB 
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

using perm = array<int, 6>;

struct op {
  int type;
  array<int, 4> args;
  op() : type(-1) {}
  op(int w, array<int, 4> a) : type(w) {
    args[0] = a[0];
    args[1] = a[1];
    args[2] = a[2];
    args[3] = a[3];
  }
  int get_type() const { return type; }
  int 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;
  int ans;
  query() : ans(-1) {}
  query(const op& o, const int a) : o(o), ans(a) {}
  int type() const { return o.get_type(); }
  int 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) {
      int wc = worst_case(cur, x);
      if (wc < best || (wc == best && (rand() & 1))) {
        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

scales.cpp: In constructor 'query::query(const op&, int)':
scales.cpp:31:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   31 |   query(const op& o, const int 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&, int)':
scales.cpp:31:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   31 |   query(const op& o, const int 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&, int)':
scales.cpp:31:19: warning: declaration of 'o' shadows a member of 'query' [-Wshadow]
   31 |   query(const op& o, const int a) : o(o), ans(a) {}
      |         ~~~~~~~~~~^
scales.cpp:28:6: note: shadowed declaration is here
   28 |   op o;
      |      ^
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
72.02381 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 78 ms 340 KB Output is partially correct
2 Partially correct 81 ms 352 KB Output is partially correct
3 Partially correct 77 ms 348 KB Output is partially correct
4 Partially correct 79 ms 348 KB Output is partially correct
5 Partially correct 81 ms 348 KB Output is partially correct
6 Partially correct 83 ms 460 KB Output is partially correct
7 Partially correct 79 ms 340 KB Output is partially correct
8 Partially correct 86 ms 340 KB Output is partially correct
9 Partially correct 78 ms 344 KB Output is partially correct
10 Partially correct 82 ms 352 KB Output is partially correct
11 Partially correct 83 ms 360 KB Output is partially correct
12 Partially correct 79 ms 340 KB Output is partially correct
13 Correct 79 ms 348 KB Output is correct
14 Partially correct 83 ms 356 KB Output is partially correct
15 Partially correct 79 ms 340 KB Output is partially correct
16 Partially correct 80 ms 344 KB Output is partially correct
17 Partially correct 85 ms 344 KB Output is partially correct
18 Partially correct 78 ms 340 KB Output is partially correct
19 Partially correct 80 ms 348 KB Output is partially correct
20 Partially correct 81 ms 344 KB Output is partially correct
21 Partially correct 81 ms 348 KB Output is partially correct
22 Partially correct 82 ms 344 KB Output is partially correct
23 Partially correct 80 ms 340 KB Output is partially correct
24 Partially correct 78 ms 348 KB Output is partially correct
25 Partially correct 94 ms 340 KB Output is partially correct
26 Partially correct 79 ms 340 KB Output is partially correct
27 Partially correct 79 ms 352 KB Output is partially correct
28 Partially correct 80 ms 340 KB Output is partially correct
29 Partially correct 81 ms 340 KB Output is partially correct
30 Partially correct 82 ms 348 KB Output is partially correct
31 Partially correct 78 ms 340 KB Output is partially correct
32 Partially correct 80 ms 340 KB Output is partially correct
33 Partially correct 81 ms 348 KB Output is partially correct
34 Partially correct 78 ms 348 KB Output is partially correct
35 Partially correct 78 ms 344 KB Output is partially correct
36 Correct 79 ms 340 KB Output is correct
37 Partially correct 83 ms 340 KB Output is partially correct
38 Partially correct 79 ms 344 KB Output is partially correct
39 Partially correct 80 ms 348 KB Output is partially correct
40 Partially correct 80 ms 344 KB Output is partially correct