oj.uz

Submission #917526

# Submission time Handle Problem Language Result Execution time Memory
917526 2024-01-28T11:37:02 Z nguyentunglam Scales (IOI15_scales) C++17
0 / 100
 263 ms 604 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);
  }
  return;
  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);
    }
  }
}

vector<vector<int> > p;

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() {

  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);
      }
      assert(worst != 0);
      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);
      }
      assert(worst != 0);
      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:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     assert(best < p.size());
      |            ~~~~~^~~~~~~~~~
scales.cpp:100:7: warning: '_t' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |       if (_t == 1) result = getLightest(_a, _b, _c);
      |       ^~
scales.cpp:111:31: warning: '_d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |       result = getNextLightest(_a, _b, _c, _d);
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp:102:40: warning: '_c' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |       if (_t == 3) result = getHeaviest(_a, _b, _c);
      |                             ~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:95:32: warning: '_b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |     cout << _a << " " << _b << " " << _c << " " << _d << " " << _t << endl;
      |                                ^~~
scales.cpp:95:19: warning: '_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |     cout << _a << " " << _b << " " << _c << " " << _d << " " << _t << endl;
      |                   ^~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 348 KB Hacked.
2 Incorrect 220 ms 348 KB Hacked.
3 Incorrect 215 ms 348 KB Hacked.
4 Incorrect 218 ms 348 KB Hacked.
5 Incorrect 222 ms 348 KB Hacked.
6 Incorrect 215 ms 496 KB Hacked.
7 Incorrect 217 ms 348 KB Hacked.
8 Incorrect 225 ms 348 KB Hacked.
9 Incorrect 216 ms 348 KB Hacked.
10 Incorrect 219 ms 348 KB Hacked.
11 Incorrect 224 ms 344 KB Hacked.
12 Incorrect 218 ms 348 KB Hacked.
13 Incorrect 215 ms 348 KB Hacked.
14 Incorrect 222 ms 348 KB Hacked.
15 Incorrect 213 ms 492 KB Hacked.
16 Incorrect 228 ms 348 KB Hacked.
17 Incorrect 221 ms 348 KB Hacked.
18 Incorrect 220 ms 348 KB Hacked.
19 Incorrect 222 ms 500 KB Hacked.
20 Incorrect 225 ms 596 KB Hacked.
21 Incorrect 218 ms 348 KB Hacked.
22 Incorrect 219 ms 348 KB Hacked.
23 Incorrect 263 ms 348 KB Hacked.
24 Incorrect 232 ms 492 KB Hacked.
25 Incorrect 220 ms 516 KB Hacked.
26 Incorrect 215 ms 348 KB Hacked.
27 Incorrect 218 ms 348 KB Hacked.
28 Incorrect 222 ms 348 KB Hacked.
29 Incorrect 219 ms 348 KB Hacked.
30 Incorrect 215 ms 348 KB Hacked.
31 Incorrect 220 ms 348 KB Hacked.
32 Incorrect 217 ms 348 KB Hacked.
33 Incorrect 224 ms 348 KB Hacked.
34 Incorrect 223 ms 604 KB Hacked.
35 Incorrect 220 ms 348 KB Hacked.
36 Incorrect 222 ms 344 KB Hacked.
37 Incorrect 217 ms 348 KB Hacked.
38 Incorrect 213 ms 348 KB Hacked.
39 Incorrect 222 ms 348 KB Hacked.
40 Incorrect 217 ms 492 KB Hacked.