Submission #390981

#	Time	Username	Problem	Language	Result	Execution time	Memory
390981		usachevd0	저울 (IOI15_scales)	C++14	9.77 / 100	1 ms	204 KiB

scales

#include <bits/stdc++.h>
#ifndef DEBUG
  #include "scales.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
  return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) {
    cerr << a[i] << ' ';
  }
  cerr << endl;
}
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}

#ifdef DEBUG
  int ord[6];
  int pos[7];
  int queries;
  void init(vector<int> vord) {
    queries = 0;
    for (int i = 0; i < 6; ++i) {
      ord[i] = vord[i];
      pos[ord[i]] = i;
    }
  }
  void answer(int* pord) {
//    mdebug(pord, 6);
//    mdebug(ord, 6);
    for (int i = 0; i < 6; ++i) {
      if (ord[i] != pord[i]) {
        assert(false);
      }
    }
  }
  bool cmp(int x, int y) {
    return pos[x] < pos[y];
  }
  int getLightest(int a, int b, int c) {
    ++queries;
    vector<int> v = {a, b, c};
    sort(all(v), cmp);
    v.resize(unique(all(v)) - v.begin());
    assert(v.size() == 3);
    return v[0];
  }
  int getHeaviest(int a, int b, int c) {
    ++queries;
    vector<int> v = {a, b, c};
    sort(all(v), cmp);
    v.resize(unique(all(v)) - v.begin());
    assert(v.size() == 3);
    return v[2];
  }
  int getMedian(int a, int b, int c) {
    ++queries;
    vector<int> v = {a, b, c};
    sort(all(v), cmp);
    v.resize(unique(all(v)) - v.begin());
    assert(v.size() == 3);
    return v[1];
  }
#endif



void init(int tests) {
}

void orderCoins() {
  mt19937 rng(time(0));

  int ord[6];
  iota(ord, ord + 6, 1);
  int le[7][7];
  memset(le, 255, sizeof le);
  for (int x = 1; x <= 6; ++x) {
    le[x][x] = 0;
  }
  auto GetLightest = [&](int a, int b, int c) -> int {
    if (le[a][b] == 1 && le[a][c] == 1) return a;
    if (le[b][a] == 1 && le[b][c] == 1) return b;
    if (le[c][a] == 1 && le[c][b] == 1) return c;
    int t = getLightest(a, b, c);
    for (int x : {a, b, c}) {
      if (x != t) {
        le[t][x] = 1;
        le[x][t] = 0;
      }
    }
    return t;
  };
  auto GetHeaviest = [&](int a, int b, int c) -> int {
    if (le[b][a] == 1 && le[c][a] == 1) return a;
    if (le[a][b] == 1 && le[c][b] == 1) return b;
    if (le[a][c] == 1 && le[b][c] == 1) return c;
    int t = getHeaviest(a, b, c);
    for (int x : {a, b, c}) {
      if (x != t) {
        le[x][t] = 1;
        le[t][x] = 0;
      }
    }
    return t;
  };
  /*auto GetMedian = [&](int a, int b, int c) -> int {
    if (le[b][a] == 1 && le[a][c] == 1 || le[c][a] == 1 && le[a][b] == 1) return a;
    if (le[a][b] == 1 && le[b][c] == 1 || le[c][b] == 1 && le[b][a] == 1) return b;
    if (le[a][c] == 1 && le[c][b] == 1 || le[b][c] == 1 && le[c][a] == 1) return c;
    return getMedian(a, b, c);
  };*/

  auto rex = [&](int x, int y) {
    vector<int> ex;
    for (int z = 1; z <= 6; ++z) {
      if (z != x && z != y) {
        ex.push_back(z);
      }
    }
    return ex[rng() % ex.size()];
  };
  
  auto cmp = [&](int x, int y) -> bool {
    if (le[x][y] != -1) {
      return le[x][y];
    }
    int t = rex(x, y);
    if (rng() % 2 == 0) {
      if (getLightest(x, y, t) == t) {
        return getHeaviest(x, y, t) == y;
      } else return getLightest(x, y, t) == x;
    } else {
      if (getHeaviest(x, y, t) == t) {
        return getLightest(x, y, t) == x;
      } else return getHeaviest(x, y, t) == y;
    }
  };
  stable_sort(ord, ord + 6, cmp);
  answer(ord);
}


#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  vector<int> ord(6);
  iota(all(ord), 1);
  int max_queries = 0;
  do {
    init(ord);
    orderCoins();
    chkmax(max_queries, queries);
  } while (next_permutation(all(ord)));
  debug(max_queries);

  return 0;
}
#endif

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:107:15: warning: unused parameter 'tests' [-Wunused-parameter]
  107 | void init(int tests) {
      |           ~~~~^~~~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:120:8: warning: variable 'GetLightest' set but not used [-Wunused-but-set-variable]
  120 |   auto GetLightest = [&](int a, int b, int c) -> int {
      |        ^~~~~~~~~~~
scales.cpp:133:8: warning: variable 'GetHeaviest' set but not used [-Wunused-but-set-variable]
  133 |   auto GetHeaviest = [&](int a, int b, int c) -> int {
      |        ^~~~~~~~~~~

• Subtask 1: 9.772211 / 100