oj.uz

답안 #917827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917827 2024-01-29T00:29:06 Z nguyentunglam 저울 (IOI15_scales) C++17
0 / 100
 467 ms 756 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) {
  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));

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

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 126 ms 344 KB Output isn't correct
2 Incorrect 64 ms 344 KB Output isn't correct
3 Incorrect 228 ms 348 KB Output isn't correct
4 Incorrect 331 ms 500 KB Output isn't correct
5 Incorrect 242 ms 348 KB Output isn't correct
6 Correct 467 ms 508 KB Output is correct
7 Incorrect 51 ms 348 KB Output isn't correct
8 Incorrect 311 ms 492 KB Output isn't correct
9 Correct 462 ms 496 KB Output is correct
10 Incorrect 342 ms 348 KB Output isn't correct
11 Correct 460 ms 596 KB Output is correct
12 Incorrect 28 ms 488 KB Output isn't correct
13 Correct 450 ms 756 KB Output is correct
14 Incorrect 256 ms 508 KB Output isn't correct
15 Incorrect 124 ms 500 KB Output isn't correct
16 Correct 456 ms 496 KB Output is correct
17 Incorrect 26 ms 344 KB Output isn't correct
18 Incorrect 325 ms 344 KB Output isn't correct
19 Incorrect 426 ms 504 KB Output isn't correct
20 Correct 456 ms 500 KB Output is correct
21 Correct 447 ms 500 KB Output is correct
22 Incorrect 128 ms 348 KB Output isn't correct
23 Incorrect 50 ms 348 KB Output isn't correct
24 Incorrect 430 ms 348 KB Output isn't correct
25 Incorrect 153 ms 504 KB Output isn't correct
26 Correct 449 ms 500 KB Output is correct
27 Incorrect 230 ms 348 KB Output isn't correct
28 Correct 456 ms 496 KB Output is correct
29 Incorrect 26 ms 348 KB Output isn't correct
30 Incorrect 150 ms 500 KB Output isn't correct
31 Correct 455 ms 620 KB Output is correct
32 Incorrect 251 ms 496 KB Output isn't correct
33 Incorrect 76 ms 608 KB Output isn't correct
34 Incorrect 103 ms 348 KB Output isn't correct
35 Correct 448 ms 488 KB Output is correct
36 Incorrect 275 ms 496 KB Output isn't correct
37 Incorrect 124 ms 348 KB Output isn't correct
38 Correct 462 ms 496 KB Output is correct
39 Correct 447 ms 344 KB Output is correct
40 Incorrect 327 ms 504 KB Output isn't correct