oj.uz

Submission #917617

# Submission time Handle Problem Language Result Execution time Memory
917617 2024-01-28T13:22:51 Z nguyentunglam Scales (IOI15_scales) C++17
76.4881 / 100
 500 ms 764 KB 
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;

mt19937 rng(1);

int n = 6;
const int T = 2;

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) {
  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() {
  shuffle(three.begin(), three.end(), rng);
  shuffle(four.begin(), four.end(), rng);
  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) {
    pair<int, int> best = make_pair(1e9, 1e9);
    int _a, _b, _c, _d, _t;

    for(auto &[a, b, c, d] : four) {
      int worst1 = 0, worst2 = 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) {
          worst2 = max(worst2, sat);
          if (worst1 < worst2) swap(worst1, worst2);
        }
      }
      if (!worst1 || worst1 == p.size()) continue;
      if (best > make_pair(worst1, worst2)) {
        best = make_pair(worst1, worst2);
        _a = a;
        _b = b;
        _c = c;
        _d = d;
        _t = 0;
      }
    }

    for(auto &[a, b, c] : three) for(int type = 3; type >= 1; type--) {
      int worst1 = 0, worst2 = 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) {
          worst2 = max(worst2, sat);
          if (worst1 < worst2) swap(worst1, worst2);
        }
      }
      if (!worst1 || worst1 == p.size()) continue;
      if (best > make_pair(worst1, worst2)) {
        best = make_pair(worst1, worst2);
        _a = a;
        _b = b;
        _c = c;
        _t = type;
      }
    }

    #ifdef ngu
    cout << _a << " " << _b << " " << _c << " " << _d << " " << _t << endl;
    #endif // ngu

    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:15:15: warning: declaration of 'T' shadows a global declaration [-Wshadow]
   15 | void init(int T) {
      |           ~~~~^
scales.cpp:8:11: note: shadowed declaration is here
    8 | const int T = 2;
      |           ^
scales.cpp:15:15: warning: unused parameter 'T' [-Wunused-parameter]
   15 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:71:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |       if (!worst1 || worst1 == p.size()) continue;
      |                      ~~~~~~~^~~~~~~~~~~
scales.cpp:92:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |       if (!worst1 || worst1 == p.size()) continue;
      |                      ~~~~~~~^~~~~~~~~~~
scales.cpp:109:7: warning: '_t' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |       if (_t == 1) result = getLightest(_a, _b, _c);
      |       ^~
scales.cpp:120:31: warning: '_d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |       result = getNextLightest(_a, _b, _c, _d);
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp:120:31: warning: '_c' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:120:31: warning: '_b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:120:31: warning: '_a' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
76.488095 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 760 KB Output is correct
2 Partially correct 447 ms 508 KB Output is partially correct
3 Partially correct 440 ms 348 KB Output is partially correct
4 Partially correct 446 ms 600 KB Output is partially correct
5 Correct 460 ms 752 KB Output is correct
6 Partially correct 447 ms 504 KB Output is partially correct
7 Correct 453 ms 596 KB Output is correct
8 Correct 447 ms 344 KB Output is correct
9 Correct 453 ms 500 KB Output is correct
10 Partially correct 455 ms 760 KB Output is partially correct
11 Partially correct 443 ms 504 KB Output is partially correct
12 Partially correct 456 ms 504 KB Output is partially correct
13 Correct 386 ms 504 KB Output is correct
14 Correct 451 ms 504 KB Output is correct
15 Correct 445 ms 504 KB Output is correct
16 Partially correct 444 ms 344 KB Output is partially correct
17 Partially correct 452 ms 504 KB Output is partially correct
18 Partially correct 444 ms 348 KB Output is partially correct
19 Correct 466 ms 732 KB Output is correct
20 Partially correct 462 ms 504 KB Output is partially correct
21 Partially correct 439 ms 504 KB Output is partially correct
22 Correct 500 ms 504 KB Output is correct
23 Correct 468 ms 348 KB Output is correct
24 Partially correct 443 ms 344 KB Output is partially correct
25 Partially correct 451 ms 756 KB Output is partially correct
26 Partially correct 457 ms 504 KB Output is partially correct
27 Correct 447 ms 504 KB Output is correct
28 Partially correct 446 ms 504 KB Output is partially correct
29 Correct 454 ms 496 KB Output is correct
30 Partially correct 441 ms 508 KB Output is partially correct
31 Correct 447 ms 504 KB Output is correct
32 Correct 445 ms 504 KB Output is correct
33 Correct 438 ms 348 KB Output is correct
34 Partially correct 442 ms 620 KB Output is partially correct
35 Partially correct 457 ms 764 KB Output is partially correct
36 Partially correct 437 ms 504 KB Output is partially correct
37 Correct 477 ms 504 KB Output is correct
38 Partially correct 497 ms 508 KB Output is partially correct
39 Partially correct 456 ms 508 KB Output is partially correct
40 Partially correct 461 ms 348 KB Output is partially correct