답안 #917532

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917532 2024-01-28T11:41:33 Z nguyentunglam 저울 (IOI15_scales) C++17
0 / 100
74 ms 648 KB
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;

int n = 6;

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) {
  vector<int> heavier;
  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 == 1e9) return ask_three(a, b, c, 1, tmp);
  return ret;
}

void orderCoins() {
  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) {
    int best = 1e9;
    int _a, _b, _c, _d, _t;
    for(auto &[a, b, c] : three) for(int type = 1; type <= 3; type++) {
      int worst = 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) worst = max(worst, sat);
      }
      if (!worst) continue;
      if (best > worst) {
        best = worst;
        _a = a;
        _b = b;
        _c = c;
        _t = type;
      }
    }
    for(auto &[a, b, c, d] : four) {
      int worst = 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) worst = max(worst, sat);
      }
      if (!worst) continue;
      if (best > worst) {
        best = worst;
        _a = a;
        _b = b;
        _c = c;
        _d = d;
        _t = 0;
      }
    }

//    if (best == p.size()) break;
    assert(best < p.size());

//    cout << _a << " " << _b << " " << _c << " " << _d << " " << _t << endl;

    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;
  for(int i = 0; i < n; i++) cerr << hidden[i] << " ";
  answer(hidden);
}

Compilation message

scales.cpp: In function 'void init(int)':
scales.cpp:12:15: warning: unused parameter 'T' [-Wunused-parameter]
   12 | void init(int T) {
      |           ~~~~^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from scales.cpp:2:
scales.cpp: In function 'void orderCoins()':
scales.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     assert(best < p.size());
      |            ~~~~~^~~~~~~~~~
scales.cpp:98:7: warning: '_t' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |       if (_t == 1) result = getLightest(_a, _b, _c);
      |       ^~
scales.cpp:110:38: warning: '_d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |       for(auto &tmp : p) if (ask_four(_a, _b, _c, _d, tmp) == result) {
      |                              ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
scales.cpp:100:40: warning: '_c' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |       if (_t == 3) result = getHeaviest(_a, _b, _c);
      |                             ~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:100:40: warning: '_b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:100:40: warning: '_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 344 KB Output isn't correct
2 Incorrect 19 ms 348 KB Output isn't correct
3 Incorrect 37 ms 348 KB Output isn't correct
4 Incorrect 19 ms 348 KB Output isn't correct
5 Incorrect 19 ms 488 KB Output isn't correct
6 Incorrect 19 ms 348 KB Output isn't correct
7 Incorrect 37 ms 348 KB Output isn't correct
8 Incorrect 19 ms 344 KB Output isn't correct
9 Incorrect 19 ms 344 KB Output isn't correct
10 Incorrect 74 ms 492 KB Output isn't correct
11 Incorrect 19 ms 348 KB Output isn't correct
12 Runtime error 22 ms 604 KB Execution killed with signal 11
13 Incorrect 19 ms 344 KB Output isn't correct
14 Incorrect 19 ms 344 KB Output isn't correct
15 Runtime error 20 ms 648 KB Execution killed with signal 11
16 Incorrect 19 ms 492 KB Output isn't correct
17 Incorrect 20 ms 344 KB Output isn't correct
18 Incorrect 19 ms 348 KB Output isn't correct
19 Incorrect 19 ms 348 KB Output isn't correct
20 Incorrect 19 ms 348 KB Output isn't correct
21 Incorrect 19 ms 344 KB Output isn't correct
22 Incorrect 19 ms 348 KB Output isn't correct
23 Incorrect 19 ms 492 KB Output isn't correct
24 Incorrect 19 ms 492 KB Output isn't correct
25 Incorrect 19 ms 348 KB Output isn't correct
26 Runtime error 41 ms 596 KB Execution killed with signal 11
27 Incorrect 19 ms 348 KB Output isn't correct
28 Runtime error 19 ms 604 KB Execution killed with signal 11
29 Incorrect 19 ms 344 KB Output isn't correct
30 Incorrect 19 ms 508 KB Output isn't correct
31 Incorrect 19 ms 348 KB Output isn't correct
32 Runtime error 38 ms 484 KB Execution killed with signal 11
33 Incorrect 37 ms 348 KB Output isn't correct
34 Incorrect 56 ms 348 KB Output isn't correct
35 Incorrect 19 ms 344 KB Output isn't correct
36 Incorrect 19 ms 348 KB Output isn't correct
37 Incorrect 19 ms 600 KB Output isn't correct
38 Incorrect 19 ms 488 KB Output isn't correct
39 Incorrect 37 ms 348 KB Output isn't correct
40 Incorrect 19 ms 348 KB Output isn't correct