Submission #391712

#	Time	Username	Problem	Language	Result	Execution time	Memory
391712		usachevd0	Scales (IOI15_scales)	C++14	100 / 100	149 ms	2440 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
  vector<int> pp;
  vector<int> ip;
  int getHeaviest(int x, int y, int z) {
    vector<int> ord = {x, y, z};
    sort(all(ord), [&](int x, int y) -> bool {
      return ip[x] < ip[y];
    });
    return ord[2];
  }
  int getLightest(int x, int y, int z) {
    vector<int> ord = {x, y, z};
    sort(all(ord), [&](int x, int y) -> bool {
      return ip[x] < ip[y];
    });
    return ord[0];
  }
  int getMedian(int x, int y, int z) {
    vector<int> ord = {x, y, z};
    sort(all(ord), [&](int x, int y) -> bool {
      return ip[x] < ip[y];
    });
    return ord[1];
  }
  int getNextLightest(int x, int y, int z, int w) {
    vector<int> ord = {x, y, z};
    sort(all(ord), [&](int x, int y) -> bool {
      return ip[x] < ip[y];
    });
    int i = 0;
    while (i < 3 && ip[ord[i]] < ip[w]) ++i;
    return ord[i % 3];
  }
  void answer(int* p) {
    for (int i = 0; i < 6; ++i) {
      assert(pp[i] == p[i]);
    }
  }
#endif


int pw3[10];

const int P = 720;
const int Q = 120;
vector<int> perm[P];
map<vector<int>, int> pid;

using Mask = array<bool, P>;
Mask fullMask;

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

  Query() {}
  Query(int _type, int a, int b, int c) {
    type = _type;
    args = {a, b, c};
  }
  Query(int _type, int a, int b, int c, int d) {
    type = _type;
    args = {a, b, c, d};
  }
} query[Q];

int ans[P][Q];

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

  ptr = 0;
  for (int a = 0; a < 6; ++a) {
    for (int b = a + 1; b < 6; ++b) {
      for (int c = b + 1; c < 6; ++c) {
        for (int type = 0; type <= 2; ++type) {
          query[ptr++] = Query(type, a, b, c);
        }
        for (int d = 0; d < 6; ++d) {
          if (d != a && d != b && d != c) {
            query[ptr++] = Query(3, a, b, c, d);
          }
        }
      }
    }
  }
  assert(ptr == Q);

  for (int pi = 0; pi < P; ++pi) {
    auto& p = perm[pi];
    vector<int> where(6);
    for (int i = 0; i < 6; ++i) {
      where[p[i]] = i;
    }
    for (int qi = 0; qi < Q; ++qi) {
      auto& q = query[qi];
      vector<pii> ord;
      for (int i = 0; i < 3; ++i) {
        ord.emplace_back(q.args[i], i);
      }
      sort(all(ord), [&](pii x, pii y) -> bool {
        return where[x.fi] < where[y.fi];
      });
      switch (q.type) {
        case 0:
          ans[pi][qi] = ord[2].se;
          break;
        case 1:
          ans[pi][qi] = ord[0].se;
          break;
        case 2:
          ans[pi][qi] = ord[1].se;
          break;
        case 3:
          int d = q.args[3];
          int i = 0;
          while (i < 3 && where[ord[i].fi] < where[d]) ++i;
          ans[pi][qi] = ord[i % 3].se;
          break;
      }
    }
  }

  pw3[0] = 1;
  for (int i = 1; i < 10; ++i) pw3[i] = pw3[i - 1] * 3;

  fill(all(fullMask), 1);
}

int Count(const Mask& mask) {
  return count(all(mask), 1);
}

map<pair<Mask, int>, bool> mem;
map<pair<Mask, int>, int> whatq;
bool brute(Mask mask, int rem = 6) {
  pair<Mask, int> key = {mask, rem};
  int cnt = Count(mask);
  if (cnt <= 1) {
    return mem[key] = true;
  }
  if (mem.count(key)) {
    return mem[key];
  }
  if (cnt > pw3[rem]) {
    return mem[key] = false;
  }
  for (int qi = 0; qi < Q; ++qi) {
    Mask nxt[3];
    for (int i = 0; i < 3; ++i) {
      fill(all(nxt[i]), 0);
    }
    for (int pi = 0; pi < P; ++pi) {
      if (mask[pi]) {
        nxt[ans[pi][qi]][pi] = 1;
      }
    }
    if (max(Count(nxt[0]), max(Count(nxt[1]), Count(nxt[2]))) <= pw3[rem - 1] && brute(nxt[0], rem - 1) && brute(nxt[1], rem - 1) && brute(nxt[2], rem - 1)) {
      whatq[key] = qi;
      return mem[key] = true;
    }
  }
  return mem[key] = false;
}



void init(int T) {
  prec();
  brute(fullMask, 6);
}

int ask(int qi) {
  auto& q = query[qi];
  switch (q.type) {
    case 0:
      return find(all(q.args), getHeaviest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
      break;
    case 1:
      return find(all(q.args), getLightest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
      break;
    case 2:
      return find(all(q.args), getMedian(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
      break;
    case 3:
      return find(all(q.args), getNextLightest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1, q.args[3] + 1) - 1) - q.args.begin();
      break;
  }
}

void orderCoins() {
  Mask mask = fullMask;
  for (int rem = 6; rem > 0; --rem) {
    int qi = whatq[{mask, rem}];
    int r = ask(qi);
    for (int pi = 0; pi < P; ++pi) {
      mask[pi] &= ans[pi][qi] == r;
    }
  }
  int pi = 0;
  while (pi < P && !mask[pi]) ++pi;
  int p[6];
  for (int i = 0; i < 6; ++i) {
    p[i] = perm[pi][i] + 1;
  }
  answer(p);
} 
 
#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  pp.resize(6);
  ip.resize(6);
  iota(all(pp), 0);
  init(-1);
  do {
    //debug(pp);
    for (int i = 0; i < 6; ++i) ip[pp[i]] = i;
    orderCoins();
  } while (next_permutation(all(pp)));
 
  return 0;
}
#endif

Compilation message (stderr)

scales.cpp: In function 'void prec()':
scales.cpp:152:11: warning: declaration of 'p' shadows a previous local [-Wshadow]
  152 |     auto& p = perm[pi];
      |           ^
scales.cpp:126:15: note: shadowed declaration is here
  126 |   vector<int> p(6);
      |               ^
scales.cpp: In function 'int Count(const Mask&)':
scales.cpp:193:15: warning: conversion from 'std::iterator_traits<const bool*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  193 |   return count(all(mask), 1);
      |          ~~~~~^~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:230:15: warning: unused parameter 'T' [-Wunused-parameter]
  230 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int ask(int)':
scales.cpp:239:94: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  239 |       return find(all(q.args), getHeaviest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp:242:94: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  242 |       return find(all(q.args), getLightest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp:245:92: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  245 |       return find(all(q.args), getMedian(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp:248:113: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  248 |       return find(all(q.args), getNextLightest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1, q.args[3] + 1) - 1) - q.args.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp:251:1: warning: control reaches end of non-void function [-Wreturn-type]
  251 | }
      | ^

• Subtask 1: 100 / 100