oj.uz

Submission #918205

# Submission time Handle Problem Language Result Execution time Memory
918205 2024-01-29T13:30:47 Z nguyentunglam Scales (IOI15_scales) C++17
100 / 100
 495 ms 752 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 == 0) 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++) if (type != 2) {
      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] : three) for(int type = 1; type <= 3; type++) if (type == 2) {
      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;
  #ifdef ngu
  for(int i = 0; i < n; i++) cerr << hidden[i] << " ";
  #endif // ngu

  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:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     assert(best < p.size());
      |            ~~~~~^~~~~~~~~~
scales.cpp:114:7: warning: '_t' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |       if (_t == 1) result = getLightest(_a, _b, _c);
      |       ^~
scales.cpp:126:38: warning: '_d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |       for(auto &tmp : p) if (ask_four(_a, _b, _c, _d, tmp) == result) {
      |                              ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
scales.cpp:116:40: warning: '_c' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |       if (_t == 3) result = getHeaviest(_a, _b, _c);
      |                             ~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:116:40: warning: '_b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:116:40: warning: '_a' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 344 KB Output is correct
2 Correct 436 ms 348 KB Output is correct
3 Correct 447 ms 348 KB Output is correct
4 Correct 451 ms 344 KB Output is correct
5 Correct 446 ms 508 KB Output is correct
6 Correct 445 ms 504 KB Output is correct
7 Correct 450 ms 484 KB Output is correct
8 Correct 443 ms 504 KB Output is correct
9 Correct 442 ms 504 KB Output is correct
10 Correct 451 ms 592 KB Output is correct
11 Correct 454 ms 504 KB Output is correct
12 Correct 442 ms 344 KB Output is correct
13 Correct 453 ms 596 KB Output is correct
14 Correct 447 ms 348 KB Output is correct
15 Correct 446 ms 504 KB Output is correct
16 Correct 451 ms 512 KB Output is correct
17 Correct 449 ms 500 KB Output is correct
18 Correct 458 ms 508 KB Output is correct
19 Correct 471 ms 508 KB Output is correct
20 Correct 479 ms 496 KB Output is correct
21 Correct 495 ms 512 KB Output is correct
22 Correct 461 ms 500 KB Output is correct
23 Correct 459 ms 504 KB Output is correct
24 Correct 454 ms 500 KB Output is correct
25 Correct 458 ms 484 KB Output is correct
26 Correct 469 ms 508 KB Output is correct
27 Correct 458 ms 500 KB Output is correct
28 Correct 459 ms 508 KB Output is correct
29 Correct 462 ms 504 KB Output is correct
30 Correct 446 ms 344 KB Output is correct
31 Correct 467 ms 512 KB Output is correct
32 Correct 443 ms 504 KB Output is correct
33 Correct 442 ms 752 KB Output is correct
34 Correct 440 ms 344 KB Output is correct
35 Correct 453 ms 504 KB Output is correct
36 Correct 465 ms 744 KB Output is correct
37 Correct 473 ms 344 KB Output is correct
38 Correct 452 ms 504 KB Output is correct
39 Correct 443 ms 512 KB Output is correct
40 Correct 439 ms 504 KB Output is correct