제출 #391014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391014		usachevd0	저울 (IOI15_scales)	C++14	71.73 / 100	122 ms	708 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;
}

mt19937 rng(228);

const int P = 720;
vector<int> perm[P];
map<vector<int>, int> perm_idx;

struct PMask {
  ll a[12];

  PMask() {
    memset(a, 0xff, sizeof a);
  }
  PMask(const PMask& oth) {
    for (int i = 0; i < 12; ++i) {
      a[i] = oth.a[i];
    }
  }

  bool has(int i) {
    return (a[i / 64] >> (i % 64)) & 1;
  }
  void enable(int i) {
    a[i / 64] |= 1ull << (i % 64);
  }

  int Count() {
    int cnt = 0;
    for (int i = 0; i < 12; ++i) {
      cnt += __builtin_popcountll(a[i]);
    }
    return cnt;
  }

  bool Unique() {
    return Count() == 1;
  }

  bool Contradict() {
    return Count() == 0;
  }

  void doZeroMask() {
    memset(a, 0, sizeof a);
  }

  bool operator == (const PMask& oth) const {
    for (int i = 0; i < 12; ++i) {
      if (a[i] != oth.a[i]) {
        return false;
      }
    }
    return true;
  }
  bool operator < (const PMask& oth) const {
    for (int i = 0; i < 12; ++i) {
      if (a[i] != oth.a[i]) {
        return a[i] < oth.a[i];
      }
    }
    return false;
  }
} ZeroMask;

struct Query {
  int tp;
  vector<int> args;

  Query(int _tp, int a, int b, int c) {
    tp = _tp;
    args = {a, b, c};
  }
  Query(int _tp, int a, int b, int c, int d) {
    tp = _tp;
    args = {a, b, c, d};
  }

  bool Valid() {
    for (int i = 0; i + 1 < args.size(); ++i) {
      for (int j = i + 1; j < args.size(); ++j) {
        if (args[i] == args[j]) {
          return false;
        }
      }
    }
    return true;
  }
};
vector<Query> qr;

int answ(int pi, int qi) {
//  debug(pi, qi);
  auto& p = perm[pi];
  auto& q = qr[qi];
//  debug(p);
//  debug(q.tp, q.args);
  static int pos[7];
  for (int i = 0; i < 6; ++i) {
    pos[p[i]] = i;
  }
  static int apos[7];
  for (int i = 0; i < 3; ++i) {
    apos[q.args[i]] = i;
  }
  vector<int> ord = vector<int>(q.args.begin(), q.args.begin() + 3);
  sort(all(ord), [&](int x, int y) -> bool {
    return pos[x] < pos[y];
  });
//  debug(ord, apos[ord[0]]);
  switch (q.tp) {
    case 0:
      return apos[ord[0]];
      break;
    case 1:
      return apos[ord[2]];
      break;
    case 2:
      return apos[ord[3]];
      break;
    case 3:
      int d = q.args[3];
      int i = 0;
      while (i < 3 && pos[ord[i]] < pos[d]) {
        ++i;
      }
      if (i == 3) {
        return apos[ord[0]];
      } else {
        return apos[ord[i]];
      }
      break;
  }
  throw;
  return -1;
}

void prec() {
  vector<int> p(6);
  iota(all(p), 1);
  int i = 0;
  do {
    perm[i] = vector<int>(all(p));
    perm_idx[perm[i]] = i;
    ++i;
  } while (next_permutation(all(p)));

  ZeroMask.doZeroMask();

  for (int tp = 0; tp <= 2; ++tp) {
    for (int a = 1; a <= 6; ++a) {
      for (int b = a + 1; b <= 6; ++b) {
        for (int c = b + 1; c <= 6; ++c) {
          qr.push_back(Query(tp, a, b, c));
        }
      }
    }
  }
  for (int a = 1; a <= 6; ++a) {
    for (int b = a + 1; b <= 6; ++b) {
      for (int c = b + 1; c <= 6; ++c) {
        for (int d = 1; d <= 6; ++d) {
          if (d != a && d != b && d != c) {
            qr.push_back(Query(3, a, b, c, d));
          }
        }
      }
    }
  }
}

map<PMask, int> w;
map<PMask, int> dp;
void dfs(PMask mask) {
//  mdebug(mask.a, 12);
  if (mask.Count() <= 1) {
    dp[mask] = 0;
    return;
  }
  if (w.count(mask)) return;
//  cerr << "a", mdebug(mask.a, 12);

  auto getNxt = [&](PMask* nxt, int qi) {
    for (int i = 0; i < 3; ++i) {
      nxt[i] = ZeroMask;
    }
    for (int pi = 0; pi < P; ++pi) {
      if (mask.has(pi)) {
        int i = answ(pi, qi);
        nxt[i].enable(pi);
      }
    }
  };

  vector<pii> guys;
  for (int qi = 0; qi < qr.size(); ++qi) {
    PMask nxt[3];
    getNxt(nxt, qi);
    /*for (int i = 0; i < 3; ++i) {
      nxt[i] = ZeroMask;
    }
    for (int pi = 0; pi < P; ++pi) {
      if (mask.has(pi)) {
        int i = answ(pi, qi);
        nxt[i].enable(pi);
      }
    }*/
    int mn = 1e9;
    int mx = -1e9;
    for (int i = 0; i < 3; ++i) {
      chkmin(mn, nxt[i].Count());
      chkmax(mx, nxt[i].Count());
    }
    guys.push_back({mx - mn, qi});
  }
  shuffle(all(guys), rng);
  sort(all(guys), [&](const pii& lhs, const pii& rhs) -> bool {
    if (lhs.fi != rhs.fi) {
      return lhs.fi < rhs.fi;
    }
    return false;
  });

  w[mask] = -1;
  dp[mask] = 1e9;
  for (int ii = 0; ii < 1; ++ii) {
    if (guys[ii].fi == 720) break;
    int qi = guys[ii].se;
//    debug(qi);

    int mx = 0;
    PMask nxt[3];
    getNxt(nxt, qi);
    /*for (int i = 0; i < 3; ++i) {
      nxt[i] = ZeroMask;
    }
    for (int pi = 0; pi < P; ++pi) {
      if (mask.has(pi)) {
        int i = answ(pi, qi);
        nxt[i].enable(pi);
      }
    }*/
    for (int i = 0; i < 3; ++i) {
//      debug(i);
//      mdebug(nxt[i].a, 12);
      for (int j = 0; j < 12; ++j) {
        assert((nxt[i].a[j] & mask.a[j]) == nxt[i].a[j]);
      }
      dfs(nxt[i]);
      chkmax(mx, dp[nxt[i]]);
    }
    if (chkmin(dp[mask], mx)) {
      w[mask] = qi;
    }
  }
  assert(w[mask] != -1);
  ++dp[mask];
}


#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];
  }
  int getNextLightest(int a, int b, int c, int d) {
    ++queries;
    vector<int> v = {a, b, c};
    sort(all(v), cmp);
    v.resize(unique(all(v)) - v.begin());
    assert(v.size() == 3);
    for (int x : v) {
      assert(x != d);
    }
    int i = 0;
    while (i < 3 && cmp(v[i], d)) {
      ++i;
    }
    return v[i % 3];
  }
#endif



void init(int tests) {
  prec();
  dfs(PMask());
  debug(dp[PMask()]);
}

int ask(int qi) {
  auto q = qr[qi];
  vector<int> v = vector<int>(q.args.begin(), q.args.begin() + 3);
  static int apos[7];
  for (int i = 0; i < 3; ++i) {
    apos[v[i]] = i;
  }
  switch (q.tp) {
    case 0:
      return apos[getLightest(v[0], v[1], v[2])];
      break;
    case 1:
      return apos[getHeaviest(v[0], v[1], v[2])];
      break;
    case 2:
      return apos[getMedian(v[0], v[1], v[2])];
      break;
    case 3:
      return apos[getNextLightest(v[0], v[1], v[2], q.args.back())];
      break;
  }
  throw;
  return -1;
}

void orderCoins() {
  PMask mask;
  while (mask.Count() != 1) {
//    mdebug(mask.a, 10);
    int qi = w[mask];
//    debug(qr[qi].tp, qr[qi].args);
    int i = ask(qi);
    PMask nxt = ZeroMask;
    for (int pi = 0; pi < P; ++pi) {
      if (mask.has(pi) && answ(pi, qi) == i) {
        nxt.enable(pi);
      }
    }
    mask = nxt;
//    swap(mask, nxt);
  }
  int pi = 0;
  while (!mask.has(pi)) ++pi;
  auto& p = perm[pi];
  int ord[6];
  for (int i = 0; i < 6; ++i) {
    ord[i] = p[i];
  }
//  mdebug(ord, 6);
  answer(ord);
}

#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  init(-1); //exit(0);

  vector<int> ord(6);
  iota(all(ord), 1);
  int max_queries = 0;
  do {
    init(ord);
    debug(ord);
    orderCoins();
    chkmax(max_queries, queries);
  } while (next_permutation(all(ord)));
  debug(max_queries);

  return 0;
}
#endif

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In member function 'bool Query::Valid()':
scales.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i + 1 < args.size(); ++i) {
      |                     ~~~~~~^~~~~~~~~~~~~
scales.cpp:134:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |       for (int j = i + 1; j < args.size(); ++j) {
      |                           ~~^~~~~~~~~~~~~
scales.cpp: In lambda function:
scales.cpp:238:16: warning: implicitly-declared 'constexpr PMask& PMask::operator=(const PMask&)' is deprecated [-Wdeprecated-copy]
  238 |       nxt[i] = ZeroMask;
      |                ^~~~~~~~
scales.cpp:68:3: note: because 'PMask' has user-provided 'PMask::PMask(const PMask&)'
   68 |   PMask(const PMask& oth) {
      |   ^~~~~
scales.cpp: In function 'void dfs(PMask)':
scales.cpp:249:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |   for (int qi = 0; qi < qr.size(); ++qi) {
      |                    ~~~^~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:43:22: warning: statement has no effect [-Wunused-value]
   43 |   #define debug(...) 1337
      |                      ^~~~
scales.cpp:383:3: note: in expansion of macro 'debug'
  383 |   debug(dp[PMask()]);
      |   ^~~~~
scales.cpp:380:15: warning: unused parameter 'tests' [-Wunused-parameter]
  380 | void init(int tests) {
      |           ~~~~^~~~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:424:12: warning: implicitly-declared 'constexpr PMask& PMask::operator=(const PMask&)' is deprecated [-Wdeprecated-copy]
  424 |     mask = nxt;
      |            ^~~
scales.cpp:68:3: note: because 'PMask' has user-provided 'PMask::PMask(const PMask&)'
   68 |   PMask(const PMask& oth) {
      |   ^~~~~

• Subtask 1: 71.72619 / 100