Submission #1150202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150202		mychecksedad	저울 (IOI15_scales)	C++17	100 / 100	56 ms	624 KiB

scales

/* Author : Mychecksdead  */
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

int sz[8] = {
  729, 243, 81, 27, 9, 3, 1, 0
};
vector<vector<int>> Q; // [0]: tp, [1...4]: query

struct state{
  int ask;
  vector<state*> go;
  state(){}
};

int get(vector<int> &vv, vector<int> &q){
  vi v(7);
  for(int i = 0; i < 6; ++i) v[vv[i]] = i;
  int A = v[q[1]];
  int B = v[q[2]];
  int C = v[q[3]];
  int D;
  if(q.size() > 4) D = v[q[4]];
  if(q[0] == 0){
    if(A > max(B, C)) return 0;
    if(B > max(A, C)) return 1;
    return 2;
  }else if(q[0] == 1){
    if(A < max(B, C)) return 0;
    if(B < max(A, C)) return 1;
    return 2;
  }else if(q[0] == 2){
    if(A < max(B, C) && A > min(B, C)) return 0;
    if(B < max(A, C) && B > min(A, C)) return 1;
    return 2;
  }else{
    vector<pii> V;
    V.pb({A, 0});
    V.pb({B, 1});
    V.pb({C, 2});
    sort(all(V));
    int pos = lower_bound(all(V), pii{D, -1}) - V.begin();
    if(pos != V.size()) return V[pos].ss;
    return V[0].ss;
  }
}
int f(state *v, vector<vector<int>> P, int dep){
  if(dep > 6 || P.size() > sz[dep]) return MOD;
  if(P.size() <= 1) return 0;
  // cout<< dep << ' '<< P.size()<<'\n';
  int res = MOD;
  for(int i = 0; i < Q.size(); ++i){
    auto q = Q[i];
    array<vector<vi>, 3> R;
    for(auto v: P){
      R[get(v, q)].pb(v);
    }
    if(max({R[0].size(), R[1].size(), R[2].size()}) > sz[dep + 1]) continue;
    state *u = new state();
    state *u1 = new state();
    state *u2 = new state();
    int ans = max({f(u, R[0], dep + 1), f(u1, R[1], dep + 1), f(u2, R[2], dep + 1)}) + 1;
    if(ans == 6 - dep){
      v->ask = i;
      v->go = vector<state*>{u, u1, u2};
      return ans;
    }
  }
  return MOD;
}
state *root;
void init(int T) {
  vector<vi> P;
  vi v = {1, 2, 3, 4, 5, 6};
  do{
    P.pb(v);
  }while(next_permutation(all(v)));
  for(int i = 0; i < 6; ++i){
    for(int j = i + 1; j < 6; ++j){
      for(int k = j + 1; k < 6; ++k){
        Q.pb({0, i + 1, j + 1, k + 1});
        Q.pb({1, i + 1, j + 1, k + 1});
        Q.pb({2, i + 1, j + 1, k + 1});
      }
    }
  }
  for(int i = 0; i < 6; ++i){
    for(int j = i + 1; j < 6; ++j){
      for(int k = j + 1; k < 6; ++k){
        for(int d = 0; d < 6; ++d) if(i != d && j != d && k != d) Q.pb({37, i + 1, j + 1, k + 1, d + 1});
      }
    }
  }
  root = new state();
  f(root, P, 0);
}

void orderCoins() {
  int W[] = {1, 2, 3, 4, 5, 6};
  state *v = root;
  vector<vector<int>> P;
  vi vv = {1, 2, 3, 4, 5, 6};
  do{
    P.pb(vv);
  }while(next_permutation(all(vv)));
  
  while(P.size()>1){
    vector<vector<int>> PP;
    int pos = v->ask;
    auto q = Q[pos];
    // for(int x: q) cout << x << ' ';
    // cout << endl;
    int to;
    if(0 == q[0]){
      to = getHeaviest(q[1], q[2], q[3]);
    }else if(1 == q[0]){
      to = getLightest(q[1], q[2], q[3]);
    }else if(2 == q[0]){
      to = getMedian(q[1], q[2], q[3]);
    }else{
      to = getNextLightest(q[1], q[2], q[3], q[4]);
    }
    to = (q[1] == to ? 0 : (q[2] == to ? 1 : 2));
    v = v->go[to];
    for(auto arr: P){
      if(get(arr, q) == to) PP.pb(arr);
    }
    P.swap(PP);
  }
  for(int j = 0; j < 6; ++j) W[j] = P[0][j];
  answer(W);
}

• Subtask 1: 100 / 100